MATH135 Lecture Notes - Lecture 14: Recurrence Relation

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Shane Bauman

Document Summary

Math 135 - lecture 14: more pomi and introduction to posi. Prove that 6 | (2n3 + 3n2 + n) for all n. Inductive hypothesis: assume p(k) is true for some k. P(k) = 6 | (2k3 + 3k2 + k) Inductive conclusion: verify that p(k + 1) is true. P(k + 1) = 6 | (2(k + 1)3 + 3(k + 1)2 + (k + 1)) = 2k3 + 6k2 + 6k + 2 + 3k2 + 6k + 3 + k + 1. Since by the inductive hypothesis 6 | (2k3 + 3k2 + k), therefore 6 | (2k3 + 3k2 + k) + 6(k2 + 2k + 1) Therefore p(k + 1) is true and by pomi, the statement holds for all n. Let p(n) be a statement that depends on n. P(1), p(2),,p(k) are all true implies that p(k + 1) is true for all k then p(n) is true for all n and.