Class Notes (836,374)
Mathematics (2,843)
MAT246H1 (30)
Regina (8)
Lecture

# MAT246 Lecture2.docx

5 Pages
115 Views

Department
Mathematics
Course
MAT246H1
Professor
Regina
Semester
Fall

Description
MAT246 Lecture 2 (2012-09-19) The Principle of Mathematical Induction: If S is any set of natural numbers with the properties that: A. 1 is in S, and B. 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: Every set of natural numbers that contains at least one element in it has a smallest element in it. n(n+1) Ex. Prove 1 + 2 + 3 + ⋯+ n − 1 + n = 2 ----- P(n) Hint: want to show that P(1) is true, and P(k) => P(k+1) Proof: A. P(1). LHS = 1, RHS = 1(1+1)= 1. That is LHS = RHS. 2 B. Assuming the above formula is true. Then assume k(k+1) P k = 1 + 2 + 3 + ⋯+ k − 1 + k =) 2 , then P k + 1 = P k + 1 + k + 1 ) k(k + 1) k k + 1 + 2(k + 1) (k + 1 (k + 2) P k + 1 = + k + 1 =) = 2 2 2 (k + 1 , k + 1 + 1- = 2 ( ) ( ) k+1 , k+1 +1- That is P k + 1 = 1 + 2 + 3 + ⋯+ k + k + 1 = 2 Thus the statement holds for all n by PMI. 2 2 2 2 n n+1 (2n+1) Theorem 2.1.3: 1 + 2 + 3 + ⋯+ n = 6 ----- P(n) Proof: 1 1+1 (2×1+1) A. P(1). LHS = 1, RHS = 6 = 1 B. Assuming above formula is true. Then assume 2 2 2 2 k k+1 (2k+1) P k = 1 + 2 + 3 + ⋯+ k = 6 , then P k + 1 = P k + k + 1 )2 k k + 1 2k + 1 ) k k + 1 2k + 1 + 6 k + 1 )2 P k + 1 = + k + 1 )2= 6 6 2 (k + 1 (2k + k + 6k + 6) (k + 1 2k + 3 (k + 2) P k + 1 = 6 = 6 (k + 1 ) (k + 1 + 1 2 k + 1 + 1 - P k + 1 = 6 ( ),( ) -,( ) - That is P k + 1 = 1 + 2 + 3 + ⋯+ k + (k + 1) = 2 k+1 k+1 +1 2 k+1 +1 6 Thus the statement holds for all n by PMI. MAT246 Lecture 2 (2012-09-19)  WOP⇔MI Proof: 1. WOP⟹MI Let S be a set of natural numbers that satisfies the hypothesis of math induction. Want to show that S = N. We are assuming that 1 is in S and if k is in S, then k+1 is in S. Suppose S ≠ N. Let T be the set of numbers that are not in S and T is not empty. By the WOP, T contains the smallest element t. t cannot be 1, since 1∈S, t-1∈S. However, the second hypothesis of MI tells us that t-1∈S, then t∈S. Contradiction exists. Thus, S = N. 2. MI⟹WOP Want to show that any non-empty set of natural numbers containing a smallest element. S(n): any set of natural numbers containing a natural number ≤ n has a least element. S(1): Suppose S contains 1. Since there is no natural numbers < 1, then 1 is the smallest element of S. S(k): any set of natural numbers containing a number ≤ k, has a smallest element. Let S be a set that contains a natural number ≤ k + 1. Are there in S any natural numbers that are ≤ k. If yes, then S has a smallest element by induction hypothesis; if no, then k+1∈S. Thus, k+1 is the smallest. So, S(k) => S(k+1), proof is done by MI. Generalized Principle of Mathematical Induction: Let m be a natural number. If S is a set of natural numbers with the properties that: A. m is in S, and B. k+1 is in S, whenever k is in S and is greater than or equal to m, then S contains every natural number greater than or equal to m. Theorem 2.1.5: n! > 2 n for n ≥ 4. Proof: use GPMI, A. P(4): LHS = 4! = 24, RHS = 2 = 16. That is LHS>RHS. B. Assuming the above formula is true, then assume k P k = k! > 2 , then P k + 1 = k + 1 k! > k + 1 2 > 2 ∙ 2 = 2 k k+1, since k + 1 > 2. k+1 That is P k + 1 = k + 1 ! > 2 Thus the statement holds for all n by GPMI. Ex. Show that number of diagonals in a convex polygon of n sides is given by the formula ( ) n(n−3) f n = 2 ,n ≥ 3 Proof: use GPMI A. n = 3, f(3)
More Less

Related notes for MAT246H1
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.