MATH135 Lecture Notes - Lecture 3: Mathematical Induction, Lead

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Janelle Resch

Document Summary

Let p(n) be a statement that depends on nez+ If: p(1), p(2), , (pb) are true and, k b and p(1), , p(k) are true. Ex: if {xn} is a sequence, define recursively by x1=1, x2=3, xn=2xn-1-xn-2 for n 3 then xn=2n-1. Base case verify that p(1), , p(b) is true. Inductive hypothesis assume p(k) is true k b. Inductive conclusion using assumption that (p1), , p(b) are true, show that. True (must explicitly state the ind. hypothesis and conclusion) We want to induct over xn=2n-1, n 3. Inductive hypothesis: assume xi=2i-1 is true ie[1, , k] Thus, by pmi, p(n) is true for n 3. Ex: let the sequence be defined by x1=0, x2=30 and xm=xm-1+6xm-2 for m 3. Proof: let p(n) be xn=2(3n)+3(-2)n, for n 1. Inductive hypothesis: assume that; xi=2(3)i+3(-2)i is true ie[1, , k], k 2. Inductive conclusion: let n=k+1, we want to prove that xk+1=2(3k+1)+3(-2)k+1. Thus, by psmi, p(n) is true n 1.