Study Guides (238,437)
Mathematics (538)
MAT246H1 (13)
Murnaghan (1)

# Summary notes

39 Pages
308 Views

School
University of Toronto St. George
Department
Mathematics
Course
MAT246H1
Professor
Murnaghan
Semester
Summer

Description
MAT246Y1a.doc Mathematical Induction Notation N := 1,2,3,}are called the natural numbers. Principle of Mathematical Induction Suppose S is a set of natural numbers (i.e. S N ). If: 1) 1S . 2) k +1S whenever k S . Then S =N . Example 2 2 2 n(n +1 2n +1) Prove for aln N the following formula hol1s:+2 ++ n = . 6 Proof: m m + 2m 1 + ) Let S = m N 12 + + 2= . 6 1 S : 1 =1 and 1 2 3 =1. 6 Assume k S . Show k +1S . 2 2 k k+ 1)(k +1) k S 1 + k+ = 6 . 12+ k+ 2+ k +1 2)= k k+1 2 k+1)+ (k+ 12)= k +1 k(2k)+1)+6 k +1) 6 6 2 2k +7 k+ 6 (k+ 1 k(+2 2 k+(3 ) =(k 1 ) 6 = 6 . So k +1S . = k +1 (k+(1 +1 2 k+(1 +1 )) 6 Extended Principle of Mathematical Induction Suppose S is a set of natural numbers (i.e. S N ). If: 3) n 0S . 4) k +1S whenever k S . Then {n0, 0 +1, 0 + 2,} S . Example Prove for n 7 that n! 3 . Proof: Let S = mN m! 3 m}. Letn = 7 . 0 7S :7!= 5040 > 3 = 2187. Assume k S . Show k +1S . k S k! 3k. Note by assumption k 7. Page 1 of 39 www.notesolution.com MAT246Y1a.doc k!(k +1) 3 ( +1 ) 3 8 ( ) 3 =( ) k+. Well Ordering Principle Every subset of N other than has a smallest element. Theorem Suppose S N . If: 1) 1S . 2) k +1S whenever k S . Then S = N . Proof: Let T = {nN nS }, i.e., T is the complement of S. Want to show that T = . This is equivalent to= N. Suppose T . Then (by well ordering principle) T has a smallest element, call it 1 So 1 1T (t1 1 because 1S ), st11S . But by assumption 2, (1 1)+1S , so1 S and t1T . Contradiction. Notation Let a,bN . Say a divides b (writea b) if b = ac for somecN . Definition pN is primeif the only divisors of p are 1 and p,p 1 . Extended Principle of Mathematical Induction Suppose S is a set of natural numbers (i.e. S N ). If: 1) n0S . 2) k +1S whenever n 0n 01, ,k S . Then n 0 n0+1, n0+ 2, } S . m = p1 pl Note: 1< m,m < n , so m,m S . It means n = mm = p1 p l 1 q l. m= q1 ql Example: False Proofs Claim: In any set of n people, all of them have the same age. Proof: n =1 . True. Assume true for k. Show for k +1. Let {p1, , pk+1}be a set of k +1 people. Consider {p1, , k}. They will all have the same age by assumption. Consider {p , , p }. They will all have the same age by assumption. 2 k+1 Page 2 of 39 www.notesolution.com MAT246Y1a.doc So the set{p1 , k+1}of k +1 people all have the same age. The proof was false because if take k = 2 T1= p 1 and T2= p 2 have no common element. Number Theory P RIME N UMBERS Lemma Suppose nN and n 1 . Then n is a product of prime numbers. Proof: Case 1: n is prime. Done! Case 2: n is not prime. Let S = nN n 1and nisa product of prime}. 2S . If 2,3,,n 1s , thennS : Since n is not prime, there is some natural number m 1,n sucm n, i.e. n = mm ,m,m N where m,m 1,n . Theorem There is no largest prime number. Proof: Assume p is the largest prime number. In particular, t{2,3a, } is the set of all primes. Let M = p + 1. Note that 2, 3, , p dont divide M. Now, M >1 , so there is some prime number q suchq M. But q 2,3,, p, so q is a new prime. Contradiction. Theorem: Fundamental Theorem of Arithmetic Every natural number not equal to 1 is a product of primes, and the primes in the product are unique (including multiplicity) except for the order in which they occur. Proof: Suppose there are natural numbers not equal to 1 with 2 distinct factorizations into primes. Then there is the smallest of such number (well-ordering), call it N. N = p p = q q . Note that all tie p s are different jhan the q s. So p qrt(sayar, 1 k 1 l 1 1 p1< q1). Let M = N p1 2 ql= q 1 2 ql p 1 2 ql= q(2 ql)(p1q 1), but also, M = N p1 2 ql= p1p 2 pk p1 2 ql= p 1( 2 pkq 2 ql). So p1p 2 pkq 2 ql= q 2 ql)p1q 1). Since p p p p q q ) p q q )p q ) p p q p q . Contradiction! 1 1 2 k 2 l 1 2 l 1 1 1 1 1 1 1 Page 3 of 39 www.notesolution.com
More Less

Related notes for MAT246H1

OR

Don't have an account?

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.