Class Notes (1,100,000)
CA (650,000)
UW (20,000)
MATH (2,000)
MATH135 (300)
Lecture 5

# Lecture 5-7 notes Lecture 5-7 notes including strong induction

This preview shows pages 1-2. to view the full 8 pages of the document. MATH 135 Winter 2009
Lectures V/VI/VII Notes
Strong Induction
Sometimes induction doesn’t work where it looks like it should. We then need to change our ap-
proach a bit. The following example is similar to examples that we’ve done earlier. Let’s try to make
“regular” induction work and see where things go wrong.
Example
A sequence {xn}is deﬁned by x1= 0, x2= 30 and xm=xm1+ 6xm2for m3.
Prove that xn= 2 ·3n+ 3 ·(2)nfor n1.
“Proof”
Let’s try to prove this by “regular” induction.
Base Case s
n= 1: x1= 0 and 2 ·31+ 3 ·(2)1= 0 so the result is true for n= 1.
n= 2 : x2= 30 and 2 ·32+ 3 ·(2)2= 30 so the result is true for n= 2.
(We use two Base Cases because there are two initial conditions.)
Induction Hypothesis
Suppose the result is true for n=k, for some kP,k1.
That is, suppose xk= 2 ·3k+ 3 ·(2)k.
CROSS OUT PREVIOUS AND REPLACE WITH:
Assume the result is true for n= 1,2, . . . , k for some kP,k2.
Induction Conclusion
Consider n=k+ 1.
Then
xk+1 =xk+ 6xk1(Range for k?)
= (2 ·3k+ 3 ·(2)k)+6xk1(by Induction Hypothesis)
P ROBLEM What about xk1? We need to know something here
= (2 ·3k+ 3 ·(2)k) + 6(2 ·3k1+ 3 ·(2)k1) (by Induction Hypothesis)
= 3k1[2 ·3+6·2] + (2)k1[3 ·(2) + 6 ·3]
= 18 ·3k1+ 12 ·(2)k1
= 2 ·3k+1 + 3 ·(2)k+1
Therefore the result is true for n=k+ 1, so holds for all nby POSI.

Only pages 1-2 are available for preview. Some parts have been intentionally blurred. The main problem is that our hypothesis needs to include both something about n=kand about
n=k1. Can we just add this? Yes:
Principle of Strong Induction (POSI)
Let P(n) be a statement that depends on nP.
If
(i) P(1) is true, and
(ii) P(1), P (2), . . . , P (k) are all true P(k+ 1) is true
then P(n) is true for all nP.
As a ﬁrst rule of thumb, we use POSI when the general case does (or might) depend on more than
one previous case. (In fact, we could use POSI all the time, but won’t and probably shouldn’t.)
Let’s go back and ﬁx the previous proof.
Questions and Notes
Did we need actually need a hypothesis that was that strong? Is there another option?
Technically, we didn’t quite use this version of POSI. We used a version with two base cases
that we could get by tweaking POSI just a bit to read:
(i) P(1), P(2) are true, and
(ii) P(1), P (2), . . . , P (k) are all true (and k2) P(k+ 1) is true
We get the same result as using the printed version of POSI. We could make this even more
general too:
(i) P(1), P(2), . . .,P(B) are all true, and
(ii) P(1), P (2), . . . , P (k) are all true (and kB)P(k+ 1) is true
It is important to understand what the diﬀerences are between POMI and POSI and to try to
get a sense of what parts of POSI we actually need in a given example.

Unlock to view full version

Only pages 1-2 are available for preview. Some parts have been intentionally blurred. Let’s try another example straight through to get a feel for how this works.
Example
A sequence {yn}is deﬁned by y1= 3, y2= 7, y3= 9 and ym+3 = 2ym+2 +ym+1 2ymfor m1.
Prove that yn= 2 + 2n+ (1)nfor all nP.
Proof
We prove this by strong induction.
Base Cases
n= 1 : 2 + 21+ (1)1= 3 = y1
n= 2 : 2 + 22+ (1)2= 7 = y2
n= 3 : 2 + 23+ (1)3= 9 = y3
so the result holds for n= 1,2,3.
Induction Hypothesis
Suppose the result holds for n= 1,2, . . . , k, for some kP,k3.
Induction Conclusion
Consider n=k+ 1. Then
yk+1 = 2yk+yk12yk2
= 2[2 + 2k+ (1)k]+[2+2k1+ (1)k1]2[2 + 2k2+ (1)k2]
(by Induction Hypothesis)
= 4 + 2 4+2k+1 + 2k12k1+ 2(1)k+ (1)k12(1)k2
= 2 + 2k+1 + (1)k1(since (1)k= (1)k2)
= 2 + 2k+1 + (1)k+1
so the result holds for n=k+ 1.
Therefore result holds for all nPby POSI.