15-251: Great Theoretical IdeasDos and Donts in Inductive ProofsConsider the problem of proving that ∀n ≥ 0, 1 + 2 + . . . + n =n(n+1)2by induction.Define the statement Sn= “1 + 2 + . . . + n =n(n+1)2”. We want to prove ∀n ≥ 0, Sn.1 An Inductive ProofBase Case:0(0+1)2= 0, and hence S0is true.I.H.: Assume that Skis true for some k ≥ 0.Inductive Step: We want to prove the statement S(k + 1). Note that1 + 2 + . . . + k + (k + 1) =k(k+1)2+ (k + 1) (by I.H.)= (k + 1)(k2+ 1)=(k+1)(k+2)2.And hence Sk+1is true.2 Common Errors and Pitfalls1. (Snis 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 Skis true.Inductive Step:Pk+1i=1i = k + 1 +Pki=1i= k + 1 + Sk= · · ·Logical propositions like Skcan’t be added to numbers. Please don’t equate proposi-tions and arithmetic f ormulas.2. (Proof going the Wrong Way) Make sure you use Skto prove Sk+1, and not the otherway around. Here is a common (wrong!) inductive step:Mistake:Inductive Step:1 + 2 + . . . + k + (k + 1) = (k + 1)(k + 2)/2k(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+1and ends using Skto prove an identity, which doesnot prove anything. Please make sure you do not assume Sk+1in an effort to prove it!3. (Assuming too much) Make sure you dont assume everything in the I.H.Mistake:I.H.: Assume that Skis true for all k.You want to prove the statement Sntrue for all n, and if you assume it is true, there isnothing left to prove! (Remember that the “Snis true for all n” is the same as saying“Skis 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”) i ndu ctionI.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 Skis 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 shorthandthat S1, S2, . . . , Sn−1, Snare all true for some n. Note that rewriting the I.H. in thisway shows that k was a red herring: you really want to prove Sn+1, not Sk+1.Correct Way:I.H.: Assume that Skis 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 Skis 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 notpart of the induction hypothesis. You need to distinguish between the Claim and theInduction 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 assumptionwhich might or might not b e true (but if you do the induction right, the inductionhypothesis will be true).Correct Way:I.H.: Assume that Skis true for all k ≤ n.6. (The Wrong Base Case.) Note that you want to prove S0, S1, etc., and hence the basecase should be S0.Mistake:Base Case:1(1+1)2= 1, and hence S1is true.Even if the rest of the proof works fine, you would have shown that S1, S2, S3, · · · areall correct. You haven’t shown that S0is true.7. (Assuming too little: Too few Base Cases.)Suppose you were given a function X(n) and need to show that the statement Snthat“the Fibonacci number Fn= X(n)” for all n ≥ 0.Mistake:Base Case: for n = 0, F0= X(0) blah blah. Hence S0is true.I.H.: Assume that Skis true for all k ≤ n.Induction Step: Now Fn= Fn−1+ Fn−2= X(n − 1) + X(n − 2) (because Sn−1andSn−2are both true), etc.If you are using Sn−1and Sn−2to prove T (n), then you better prove the base case forS0and S1in order to prove S2. Else you have shown S0is true, but have no way toprove S1using the above proof—S0is not a base case, and to use induction, we’d needS0and S−1. But there is no S−1!!!Remember the domino principle: the above induction uses the fact that “if two con-secutive 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
View Full Document
Unlocking...