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 3.
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