MAT246H1 Lecture Notes - Natural Number, Mathematical Induction
Document Summary
If s is any set of natural numbers with the properties that: 1 is in s, and, k+1 is in s whenever k is any number is s, then s is the set of all natural numbers. The well-ordering of the natural numbers: in it. Every set of natural numbers that contains at least one element in it has a smallest element. Prove 1 + 2 + 3 + + (n 1) + n = n(n+1) Hint: want to show that p(1) is true, and p(k) => p(k+1) That is lhs = rhs: assuming the above formula is true. P(k) = 1 + 2 + 3 + + (k 1) + k = P(k + 1) = p(k + 1) + (k + 1) k(k+1) + (k + 1) = k(k + 1) + 2(k + 1) 2 (k + 1),(k + 1) + 1-
