15 251 Great Theoretical Ideas Dos and Donts in Inductive Proofs Consider the problem of proving that n 0 1 2 n Define the statement Sn 1 2 n 1 n n 1 2 n n 1 2 by induction We want to prove n 0 Sn An Inductive Proof Base Case 0 0 1 2 0 and hence S0 is true I H Assume that Sk is true for some k 0 Inductive Step We want to prove the statement S k 1 Note that 1 2 k k 1 k k 1 2 k 1 k 1 k2 k 1 k 2 2 by I H 1 And hence Sk 1 is true 2 Common Errors and Pitfalls 1 Sn is a statement not a value You cannot make statements like Sk k 1 Sk 1 much the same as you cannot add k to the statement The earth is round Mistake I H Assume that Sk is true Inductive Step Pk 1 i 1 P i k 1 ki 1 i k 1 Sk Logical propositions like Sk can t be added to numbers Please don t equate propositions and arithmetic formulas 2 Proof going the Wrong Way Make sure you use Sk to prove Sk 1 and not the other way around Here is a common wrong inductive step Mistake Inductive Step 1 2 k k 1 k 1 k 2 2 k k 1 2 k 1 k 1 k 2 2 k 1 k 2 2 k 1 k 2 2 The proof above starts off with Sk 1 and ends using Sk to prove an identity which does not prove anything Please make sure you do not assume Sk 1 in an effort to prove it 3 Assuming too much Make sure you dont assume everything in the I H Mistake I H Assume that Sk is true for all k You want to prove the statement Sn true for all n and if you assume it is true there is nothing left to prove Remember that the Sn is true for all n is the same as saying Sk is true for all k Correct Way I H Assume that S k is true for some k or if you want to use all previous strong induction I H Assume for some k that S j is true for all j k 4 The case of the missing n Consider the following I H and inductive step Mistake I H Assume that Sk is true for all k n Inductive Step We want to prove Sk 1 What is k Where has n disappeared The induction hypothesis is saying in shorthand that S1 S2 Sn 1 Sn are all true for some n Note that rewriting the I H in this way shows that k was a red herring you really want to prove Sn 1 not Sk 1 Correct Way I H Assume that Sk is true for all k n Inductive Step We want to prove Sn 1 5 Extra stuff in the I H Consider the following I H Mistake I H Assume that Sk is true for all k n Then Sn 1 Note that entire thing has been made part of the hypothesis including the bolded part The second part Then Sn 1 is what you want to show in the inductive step it is not part of the induction hypothesis You need to distinguish between the Claim and the Induction Hypothesis The Claim is the statement you want to prove i e n 0 Sn whereas the Induction Hypothesis is an assumption you make i e 0 k n Sn which you use to prove the next statement i e Sn 1 The I H is an assumption which might or might not be true but if you do the induction right the induction hypothesis will be true Correct Way I H Assume that Sk is true for all k n 6 The Wrong Base Case Note that you want to prove S0 S1 etc and hence the base case should be S0 Mistake Base Case 1 1 1 2 1 and hence S1 is true Even if the rest of the proof works fine you would have shown that S1 S2 S3 are all correct You haven t shown that S0 is true 7 Assuming too little Too few Base Cases Suppose you were given a function X n and need to show that the statement Sn that the Fibonacci number Fn X n for all n 0 Mistake Base Case for n 0 F0 X 0 blah blah Hence S0 is true I H Assume that Sk is true for all k n Induction Step Now Fn Fn 1 Fn 2 X n 1 X n 2 because Sn 1 and Sn 2 are both true etc If you are using Sn 1 and Sn 2 to prove T n then you better prove the base case for S0 and S1 in order to prove S2 Else you have shown S0 is true but have no way to prove S1 using the above proof S0 is not a base case and to use induction we d need S0 and S 1 But there is no S 1 Remember the domino principle the above induction uses the fact that if two consecutive dominoes fall the next one will fall To now infer that all the dominoes fall you must show that the first two dominoes fall And hence you need two base cases
View Full Document
Unlocking...