Induction ill The problem is that too few base cases are considered. This immediately raises a larger question: How many base cases must I consider? The answer goes back to the strong induction axiom. In order to prove P(n) for alln>0, you must prove all of the following 口1.P(0) 日2. P(O)implies P(1) 3. P(O)and P(1)imply P(2) d 4. P(O), P(1), and P(2)imply P(3) 5. P(O), P(1), P(2)and P(3)imply P(4) You can regard this as a scorecard for strong induction proofs; if you cant check off ev ery box, the proof is bogus. For example, in the "proof"above, we established the first statement under the base case heading. The argument under the inductive step heading es- tablished statements 3, 4, 5, etc. This argument does not work for n= l, because it relies on the assumption P(n-2). ) So heres the scorecard a 2. P(O) implies P(1) X 3. P(O)and P() imply P(2) X 4. P(0), P(1), and P(2)imply P(3) X 5. P(0), P(1), P(2)and P(3)imply P(4 In order to complete the proof, we would need to show that P(O)implies P(1). But we can not in this case, since P(1)is actually false; the Fibonacci number F1= l is odd 4.4 Choosing the Wrong Induction Variable Many problems involve several different natural-valued random variables. For exampl Theoren8. For all integers k≥0andr≥2 1+T+r+.+rk1-rk+1 We could try an induction argument based on the variable r or based on the variable k. One choice(k) leads to prompt success and the other(r)leads to disaster. How are yo to know which is which? There is no general answer, though we'l try to provide guidance from time to time For example, when proving a property of a system that changes in discrete time steps, use induction on the number of steps. Your best course is to avoid fixating exclusively on one variable; if the proof doesnt work out, try induction on another variable10 Induction III The problem is that too few base cases are considered. This immediately raises a larger question: “How many base cases must I consider?” The answer goes back to the strong induction axiom. In order to prove P(n) for all n ≥ 0, you must prove all of the following: � 1. P(0) � 2. P(0) implies P(1) � 3. P(0) and P(1) imply P(2) � 4. P(0), P(1), and P(2) imply P(3) � 5. P(0), P(1), P(2) and P(3) imply P(4) . . . . . . etc. You can regard this as a scorecard for strong induction proofs; if you can’t check off ev￾ery box, the proof is bogus. For example, in the “proof” above, we established the first statement under the base case heading. The argument under the inductive step heading es￾tablished statements 3, 4, 5, etc. (This argument does not work for n = 1, because it relies on the assumption P(n − 2).) So here’s the scorecard: ×� � ×� ×� ×� 1. P(0) 2. P(0) implies P(1) 3. P(0) and P(1) imply P(2) 4. P(0), P(1), and P(2) imply P(3) 5. P(0), P(1), P(2) and P(3) imply P(4) . . . . . . etc. In order to complete the proof, we would need to show that P(0) implies P(1). But we can not in this case, since P(1) is actually false; the Fibonacci number F1 = 1 is odd. 4.4 Choosing the Wrong Induction Variable Many problems involve several different natural­valued random variables. For example: Theorem 8. For all integers k ≥ 0 and r ≥ 2: k 1 + r + r 2 + . . . + r = 1 − rk+1 1 − r We could try an induction argument based on the variable r or based on the variable k. One choice (k) leads to prompt success and the other (r) leads to disaster. How are you to know which is which? There is no general answer, though we’ll try to provide guidance from time to time. For example, when proving a property of a system that changes in discrete time steps, use induction on the number of steps. Your best course is to avoid fixating exclusively on one variable; if the proof doesn’t work out, try induction on another variable