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

MAT246 Lecture2.docx

5 Pages
115 Views
Unlock Document

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

Log In


OR

Join OneClass

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

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit