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