Comp 363 Induction Review

Strong induction Theorem.

Given statements P(n) for integers n >= a,
let I(n) be the inductive statement: 

(P(k) for all k with a <= k < n) ==> P(n)

Then the hypotheses

P(a) is true (the basis)
I(n) is true for all n > a  (the induction hypothesis)

imply the conclusion that

P(n) is true for all n >= a

The number a is the starting point:  often 0 or 1, sometimes another number.

Issues:

Basic mechanics: basis, induction step, distingush k and n
Being creative relating some smaller cases P(k), k < n, to P(n), then generalizing
Anti-intuitive fact:  A stronger statement may be easier to prove by induction!


Example for the basic mechanics:

1.  Prove ∑ t=0 to n ( 2t) = 2n+1 - 1  for n = 0, 1, 2,3, ...

P(n) is the statement:

∑ t=0 to n ( 2t) = 2n+1 - 1

The value of a is 0.

Basis, when n = 0:

left side:  ∑ t=0 to 0 ( 2t) =  20 = 1 
right side:   20+1 - 1 = 2 -1 = 1  = left side; done

Inductive step:  Let n > a.

Suppose P(k),  for k = 0,1, ... n-1
   ∑ t=0 to k ( 2t) = 2k+1 - 1  for 0,1, ... n-1
Need to show P(n):
   ∑ t=0 to n ( 2t) = 2n+1 - 1

proof:  

The "creative part" here, relating P(n) to earlier parts, is just seeing that you can split off the last term.  (This is basically it for most all summation equations done by induction).  The rest is just grinding through the algebra:
left hand side = [ ∑ t=0 to n-1 ( 2t) ]  + 2n   
= 2n-1+1 - 1  + 2n using assumed P(n-1); now follow algebra to the end...
= 2n - 1  + 2n
= 2*2n - 1
= 2n+1 - 1  the RHS !!!

2.  A binary tree has one more more nil subtree than nodes.

Two recursive approaches!  Think how to relate earlier cases!

? pretest 1b?

3.  In class, will "prove" by induction that all in any sized class will always get the same grade.  Find the fallacy.

4.  The sum of the cubes of any three consecutive integers is divisible by 9.

5.  At Costco I can buy different sized packages of paper, containing 4 reams or 7 reams or 10 reams.
That means I cannot buy exactly 1, 2, 3, 5, 6, 9 or 13 reams of paper.
Prove I can buy any exact number of reams > 13.  (Hint: the base case is not what you might expect without some thought.)

(Similar but computationally harder problem with Chicken McNuggets:  in past years I could buy 6, 9, or 20:  what is the largest number I could NOT buy?)

6.  Prove 1 + 22 + ... + n2 > n3 / 3  In other words:
Prove ∑ t=1 to n ( t2) >  n3 / 3  for n = 1, 2,3, ...

What about the weaker statement:

∑ t=1 to n ( n2) >  n2.5 / 3  for n = 1, 2,3, ...

This follows from the result above, but you could not prove it using a similar method:  the stronger statement is easier to prove.  Does that make sense?

Similar logic to cube case to go from 20 to 21 fails:
(1.0/3)*20**2.5 + 21*2 - (1.0/3)*21**2.5
= -35.353833158564498
so
(1.0/3)*20**2.5 + 21*2  < (1.0/3)*21**2.5

On to the general Intro