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=xm−1+ 6xm−2for m≥3.

Prove that xn= 2 ·3n+ 3 ·(−2)nfor n≥1.

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

TO ADD:

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 k∈P,k≥1.

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 k∈P,k≥2.

Induction Conclusion

Consider n=k+ 1.

Then

xk+1 =xk+ 6xk−1(Range for k?)

= (2 ·3k+ 3 ·(−2)k)+6xk−1(by Induction Hypothesis)

P ROBLEM What about xk−1? We need to know something here

= (2 ·3k+ 3 ·(−2)k) + 6(2 ·3k−1+ 3 ·(−2)k−1) (by Induction Hypothesis)

= 3k−1[2 ·3+6·2] + (−2)k−1[3 ·(−2) + 6 ·3]

= 18 ·3k−1+ 12 ·(−2)k−1

= 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=k−1. Can we just add this? Yes:

Principle of Strong Induction (POSI)

Let P(n) be a statement that depends on n∈P.

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 n∈P.

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 k≥2) ⇒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 k≥B)⇒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.

###### You're Reading a Preview

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 m≥1.

Prove that yn= 2 + 2n+ (−1)nfor all n∈P.

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 k∈P,k≥3.

Induction Conclusion

Consider n=k+ 1. Then

yk+1 = 2yk+yk−1−2yk−2

= 2[2 + 2k+ (−1)k]+[2+2k−1+ (−1)k−1]−2[2 + 2k−2+ (−1)k−2]

(by Induction Hypothesis)

= 4 + 2 −4+2k+1 + 2k−1−2k−1+ 2(−1)k+ (−1)k−1−2(−1)k−2

= 2 + 2k+1 + (−1)k−1(since (−1)k= (−1)k−2)

= 2 + 2k+1 + (−1)k+1

so the result holds for n=k+ 1.

Therefore result holds for all n∈Pby POSI.

###### You're Reading a Preview

Unlock to view full version