SUNY Geneseo Department of Computer Science

Introduction to Induction

{Date}

CSci 240, Spring 2007
Prof. Doug Baldwin

Misc

Phi Beta Kappa Lecture

David Kendall, "The Great War Today"
- (World War I as seen through roughly a century's worth of subsequent history and literature)
Monday, Feb. 5, 4:30 PM, Newton 203

Section 7.1.1

Proving things about recursive algorithms
Induction as a way of proving mathematical theorems
- Base case (smallest number that would be true in theorem)
- Inductive case (inference from base case?)
- Prove true for any given k and k-1?
- Truth keeps going from k-1 to k, and so on
Sum of a range of numbers as example
- Sum 1 + 2 + 3 + ... + n = n(n+1)/2
- First prove that this equation holds for base case
- Then substitute k-1 for n
- Then 1 + 2 + ... + k = ( 1 + 2 + ... + k-1 ) + k

How/why induction works

Consider 1 + 2 + 3 + ... n = n(n+1)/2
Is this true for n = 1?
- 1 = 1(1+1)/2 ?
- Yes! 1(1+1)/2 = 1 x 2/2 = 1
How about n = 2?
- 1 + 2 = 3
- 2(2+1)/2 = 2(3)/2 = 6/2 = 3
n = 3?
- 1 + 2 + 3 = 6
- 3(3+1)/2 = 6
n = 4?
- 1 + 2 + 3 + 4 = 10
- 4(4+1)/2 = 4(5)/2 = 10
Can we simplify the reasoning?
- Sum for k can be computed from sum for k-1, which someone else just evaluated
- How about n(n+1)/2 - compute this for k from k-1?
  - How does k(k+1)/2 compare to (k-1)(k)/2?
  - (k² + k)/2 vs (k² - k)/2
  - k²/2 + k/2 vs k²/2 - k/2
  - i.e., add k to the previous "n(n+1)/2" expression to get your own value of this expression
- So of course your "1 + 2 + ... + k" part is going to be equal to your "(k²/2 - k/2) + k." Both are calculated by adding k to terms that the previous person just showed were equal.
So now everybody (except the guy who has to do the first value) can prove their part by pointing to what the person before proved and the general rule that k(k+1)/2 = (k-1)k/2 + k. This idea of an initial proof (base case) and a general rule that lets you extend a theorem from one number to the next is the heart of induction.

Applying induction to recursive algorithms

Read section 7.1.2