V Adamchik 21 127 Concepts of Mathematics Mathematical Induction Victor Adamchik Fall of 2005 Lecture 2 out of three Plan 1 Strong Induction 2 Faulty Inductions 3 Induction and the Least Element Principal Strong Induction Fibonacci Numbers Fibonacci number Fn is defined as the sum of two previous Fibonacci numbers Fn F1 Fn Fn 1 1 F0 2 0 Claim Fibonacci numbers are growing exponentially n 2 Fn where n 2 is the golden ratio 1 2 5 Proof Base case n 2 F2 2 2 1 V Adamchik 21 127 Concepts of Mathematics Inductive hypothesis assume the following n 2 Fn Fn n 3 1 Note we need two assumptions Prove that Fn n 1 1 We start with the definition Fn Fn 1 Fn 1 Next we use the inductive hypothesis to obtain Fn 1 Fn Fn n 2 1 n 3 n 3 1 Now we use the property of the golden ratio prove this 2 1 Substituting this into the previous formula we get Fn n 3 1 n 1 1 Question Where would be the proof failed if you attempted to prove Fn n 2 Formal Definition The weak form induction is stated as P n0 n n0 P n Pn 1 Here P n0 is a base case and P n is the inductive hypothesis To prove that P n is true for n n0 we have to 1 show that P n0 is true 2 show that P n Pn 1 is true for n n0 V Adamchik 21 127 Concepts of Mathematics A proof by strong induction only differs from the above in the Inductive Hypothesis step Prove that P n 1 is true whenever P k is true for all k such that 0 k n Here is the formal definition P0 P1 P n Pn 1 This is called strong induction because you might need some or all previous case to prove the n 1 case Breaking Chocolate Bar A chocolate bar consists of a number of squares say n 0 arranged in a rectangular pattern You split the bar into small squares always breaking along the lines between the squares What is the minimum number of breaks Claim It takes n 1 breaks Proof Let P n denote the number of breaks needed to split a bar with n squares Base step P 1 0 is true Induction step Assume that P k is true for 2 Prove that P n 1 k n n under the above assumption Break a bar into two pieces of sizes n1 and n2 so that n1 hypothesis P n1 n1 1 P n2 n2 1 Hence the total number of breaks is 1 n1 1 n2 1 n n2 n 1 By inductive V Adamchik 21 127 Concepts of Mathematics How to justify the proof by strong induction The proof is by contradiction Suppose that some statements in the list P 1 P n were actually false We choose the first false statement say P m where m 0 Now we know that P 0 P 1 P m 1 are true Then by inductive hypothesis P m logically follows from P 0 P 1 P m 1 Therefore P m is true Contradiction Binary Search The number of comparisons used during binary search in a table of size n in the worst case described by the recurrence an a n2 1 a1 1 with the solution an Proof Base case a1 log2 1 1 Inductive hypothesis Assume ak Inductive step prove for k 0 1 log2 n 1 1 log2 k 1 for k an log2 n 2 n n 1 We start with an a n2 1 and make a use of inductive hypothesis a n2 to obtain log2 n 2 1 1 V Adamchik 21 127 Concepts of Mathematics an Let n is even n n 2 2 2 p then a2 p Let n is odd n log2 log2 p 2p 2 log2 2 p log2 2p 1 2 log2 2 2 log2 2 p 1 1 then a2 p 1 2 log2 2 p 1 1 Faulty Inductions Example 1 Claim Every positive integer n 2 has a unique prime factorization Proof Base step P 2 is true Induction step Assume that P k is true for 2 Prove that P n k n 1 is true There are two possibilities Case 1 n 1 is prime Then we are done Case 2 n 1 is composite Let n p q where 1 1 p q n 1 By inductive hypothesis p and q have unique factorizations Since the product of two unique factorizations is again unique we conclude the proof QED Explanation n 1 p q is NOT unique Example 2 Claim 6 n 0 for all n 0 Base step Clearly 6 0 0 V Adamchik 21 127 Concepts of Mathematics Induction step Assume that 6 k We need to show that 6 n Write n 1 a 0 for all 0 k n 1 is 0 b where a 0 and b 0 are natural numbers less that n have 6a 0 and 6 b 0 Therefore 6 n 1 6a 6b 0 0 0 Explanation We cannot write 1 as the sum of two natural numbers Example 3 Claim All Fibonacci numbers are even Proof by strong induction Base step Clearly F0 0 which is even IH Assume that Fk are even for all 0 k IS We need to show that Fn 1 n is even It is easy By definition Fn Fn and Fn 1 1 Fn Fn 1 are even by inductive hypothesis Thus Fn Explanation Fn 1 Fn Fn 1 is not valid for n 0 1 is even QED 1 By IH we V Adamchik 21 127 Concepts of Mathematics Induction and the Least Element Principal Weak vs Strong These two forms of induction are equivalent They only differ from each other from the point of view of writing a proof It is always possible to convert a proof using one form of induction into the other The conversion from weak to strong form is trivial because a weak form is already a strong form The conversion from a strong form into a weak form is more interesting Here are two forms P n0 P n0 n n n0 P n0 n0 P n P n0 Pn 1 1 P n Pn 1 We introduce a new hypothesis Q n defined by Qn P n0 P n0 1 P n The base step is identical in both cases namely Q n0 The inductive step is Qn Pn 1 Since Q n implies itself we rewrite the above statement as Qn Qn Pn 1 which is equivalent by definition of Q Qn Qn 1 Therefore the strong induction in P can be written as a weak induction in Q Q n0 n n0 Q n Qn 1 V Adamchik 21 127 Concepts of Mathematics Inductions vs the Least Principal Element Least Element Principal or Least Number Principal or Well Ordering Principle Each non empty subset of has a least element In this section we prove the following Theorem Induction …