MATH135 Lecture 5: Lecture 5-7 notes Lecture 5-7 notes including strong induction

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Mike Eden

Document Summary

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. Regular induction work and see where things go wrong. A sequence {xn} is de ned by x1 = 0, x2 = 30 and xm = xm 1 + 6xm 2 for m 3. Prove that xn = 2 3n + 3 ( 2)n for n 1. 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. )