Note 2 for MATH 300 at UMass
Note 2 for MATH 300 at UMass
Popular in Course
Popular in Department
This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Note 2 for MATH 300 at UMass
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Math 300 Fall 2008 Note 2 Zhigang Han7 Umass at Amherst 1 Mathematical Induction 11 Mathematical Induction o Principle of Mathematical Induction Let Pn be a statement depending on n E N If 1 P1 is TRUE 2 Vk 211 Pk 1 then Pn is TRUE for all n E N Rmk Step 1 is the base case check Step 2 is the induction step To prove step 27 we assume Pk is TRUE induction hypothesis7 and use this to prove Pk 1 is TRUE Rmk The Principle of Mathematical Induction is an immediate con sequence of the wellordering principle which states that any nonempty subset of N always contains a smallest element Try to prove yourself that the well ordering principle implies the principle of mathematical induction Eg 1 Provethat12nforalln ll Eg 2 Provethat 1222n2 H2foralln ll V L Rmk One can use sigma notation to rewrite Eg 2 as Z i2 i0 Rmk In all the examples above7 we need to know the answer before using the mathematical induction to prove it What ifwe are not given the answer nn 12n 1 6 V L V L Eg 3 Find the sum and 22 directly i0 i0 V L Eg 4 Find the sum 23 then use mathematical induction to prove it i0 Eg 5 Prove that z 7 y contains the factor x 7 y for all n E N Eg 6 What s the maximum number of regions can 71 lines divide a plane into Prove your result Eg 7 Tower of Hanoi puzzle The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883 We are given a tower of n disks initially stacked in increasing size on one of three pegs The objective is to transfer the entire tower to one of the other pegs moving only one disk at a time and never a larger one onto a smaller Prove that one can solve the puzzle by 2 7 1 moves Eg 8 The following argument is intended to prove by mathematical induc tion that all horses are of the same color Find the error Proof If there is only one horse there is only one color ii Assume that for any set of k horses there is only one color Now look at any set of k 1 horses We order them as 1 2 3 k k 1 Consider the sets 123 k and 234 k 1 Each is a set of only k horses therefore within each there is only one color But the two sets overlap so there must be only one color among all k 1 horses This proves that all horses are of the same color Variations of mathematical induction 0 The base case does not have to be P1 For instance to prove V71 2 2 Pn the base case should be P2 0 Multiple base cases lfP1 and P2 are both TRUE and for all k 2 1 Pk A Pk 1 Pk 2 then Pm is TRUE for all n e N 0 Strong Mathematical Induction lf P1 is TRUE and for all k 2 1 P1 AP2 A APk Pk 1 then Pm is TRUE for all n e N Rmk The well ordering principle implies the strong mathematical in duction Prove it ii Clearly7 the strong mathematical lnduction implies the mathematical induction Can you prove it In fact7 one can show these two forms of mathematical induction are equivalent Eg 9 Use Strong Mathematical lnduction to prove that every integer greater than or equal to 2 has a prime factor 12 Recursion Def 1 A recursion is a method of de ning functions in which the function calls itself The recursion continues until it reaches the base or stopping case Rmk There may be one or more stopping cases Eg 1 and 2 below have one stopping case7 while Eg 3 has two stopping cases Eg 1 fn fn71 71 ifn 2 2 and f1 1 Eg 2 anan1mn1 15ifn22anda1 Eg 3 Fibonacci Series Fn n11Fn12 if n 2 3 and F2 1F1 1 Eg 4 Prove that in Eg17 n yLZ Hl for all n 1 Eg 5 Prove that in Eg 201 L for all n 1 Eg 6 Prove that in Eg 37 Fn 7 for all n 1 Eg 7 Use mathematical induction to prove the following formulas i fn fn71 2fn72 if 71 Z 3 and f2 57101 2 Answers fn 2 17 71 ii an QanA 7 Qan2 if n 2 3 and a1 2 a2 0 Answers an 1 1 7 iii gn 4gn1 7 4gn2 if n 2 3 and 91 67 92 20 Answers gn 2n 1 2
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'