Induction Ill Po!. We use induction.LetP(m)be“12+22+….+n2=n(2n+1)(n+1)/6′ Base case,P(0)=20+)0+1=0 Inductive Step P(n)+(n+1)2 7(2n+1)(n+1 6 (n+1)(2m+1)+1)mn+2 6 =P(n+1) Remember, an induction hypothesis is a predicate P(n), which is a statement that is true or false depending on the value of n. In particular, P(n) has no a numerical value Adding P(n)is like trying to divide by a pomegranate. It makes no sense 4.3 Too Few base cases The Fibonacci numbers Fo, Fl, F2,... are defined recursively as follows: (Fn-1+Fn-2 when n≥2 Thus the first few Fibonacci numbers are,1, 1, 2, 3, 5,8,.... Each number is the sum of its two predecessors, except for the first two Well use Fibonacci numbers to demonstrate a error that usually comes up in connec tion with strong induction proofs False claim z. all fibonacci numbers are even Proof. We use strong induction. Let P(n) be the proposition that Fn is even Base case. Fo=0 is even, so P(O) is true Inductive step. Assume P(0),., P(n-1)to prove P(n). Now Fn= Fn-1+ Fn nd Fn- and Fn-2 are both even by assumptions P(n-1)and P(n-2), so Fn is also even By induction, all Fibonacci numbers are evenInduction III 9 2 Proof. We use induction. Let P(n) be “12 + 22 + . . . + n = n(2n + 1)(n + 1)/6”. Base case. P(0) = 0(2·0+1)(0+1) = 0 6 Inductive Step. P(n) + (n + 1)2 = n(2n + 1)(n + 1) 1 ) 2 + (n 6 (n + 1)(2(n + 1) + 1)(n + 2) = 6 = P(n + 1) × Remember, an induction hypothesis is a predicate P(n), which is a statement that is true or false depending on the value of n. In particular, P(n) has no a numerical value. Adding P(n) is like trying to divide by a pomegranate. It makes no sense. 4.3 Too Few Base Cases The Fibonacci numbers F0, F1, F2, . . . are defined recursively as follows: ⎧ ⎪⎨ ⎪⎩ 0 when n = 0 Fn = 1 when n = 1 Fn−1 + Fn−2 when n ≥ 2 Thus, the first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, . . . . Each number is the sum of its two predecessors, except for the first two. We’ll use Fibonacci numbers to demonstrate a error that usually comes up in connec￾tion with strong induction proofs. False Claim 7. All Fibonacci numbers are even. Proof. We use strong induction. Let P(n) be the proposition that Fn is even. Base case. F0 = 0 is even, so P(0) is true. Inductive step. Assume P(0), . . . , P(n − 1) to prove P(n). Now Fn = Fn−1 + Fn−2 and Fn−1 and Fn−2 are both even by assumptions P(n−1) and P(n−2), so Fn is also even. By induction, all Fibonacci numbers are even. ×