SUNY Geneseo Department of Computer Science
Introduction
to Induction
{Date}
CSci 141, Fall 2003
Prof. Doug Baldwin
Return to
List of Lectures
Previous Lecture
Questions?
Find red tile
- At least 1 red tile between robot annd wall, robot should stop as soon
as it find itself on red
![[Robot with a Red Tile Between It and Wall]](redtiles.gif)
Reading Summary
Chapter 7 through Section 7.1.1
What induction is
- Generalization of observations to universal rules
- e.g., seeing sun set many times, concluding it always sets
Sum of first natural numbers
First part OK, sketchy on second
![[Big Sigma Means Adding a Series of Numbers]](sigma.gif)
Proof about sum of first n naturals
![[Proof that Sum of the First n Naturals is n(n+1)/2]](sumi.gif)
Structure of induction
- Base case
- Goal: find any number that the claim is true of
- Induction step
- Assume theorem true of k-1
- Use assumption to show theorem true of k
- Goal: prove that whenever the claim holds of k-1, then it must also
be true k
Sum of first powers of 2
What does "big sigma" do?
For Wednesday
Review proof about sum of first powers of 2
Be ready with old mini-assignment, i.e., use induction to show that whenever
n >= 4, n! > 2n
Next Lecture