MATH145 Lecture Notes - Lecture 16: Mathematical Induction

• School: University of Waterloo
• Department: Mathematics
• Course: MATH145
• Professor: Stephen New

Document Summary

Let f (n) be a statement about an integer n. let m z. Suppose that for all k m, if f (k) is true then f (k + 1) is true. Let f (n) be a statement about an integer and let m z. Alternatively, suppose f (k 1) prove f (k) Strong mathematical induction let f (n) be a statement about an integer n and let m z. Suppose that for all n m, if f (k) for all k z with m k < n, then f (n) is true. Then f (n) is true for all n m. Let g(n) be a statement f(n) is true for all k z with m k < n . Note that g(m) is true vacuously. (since there is no value of k z with m k < n) Suppose g(n) is true, that is f (n) is true for all k z with m k < n .