The powers of a function f: A → A are defined recursively by[BB] What is wrong with the fo...

The powers of a function f: A → A are defined recursively by

[BB] What is wrong with the following argument, which purports to prove that all the Fibonacci numbers after the first two are even?

Let fn denote the nth term of the Fibonacci sequence. We prove that ƒn is even for all n ≥ 3 using the strong form of the Principle of Mathematical Induction, The Fibonacci sequence begins 1, 1,2. Certainly, f3 = 2 is even and so the assertion is true for n0 = 3. Now let k > 3 be an integer and assume that the assertion is true for all n, 3 ≤ n k; that is, assume that ƒn is even for all n < k. We wish to show that the assertion is true for n = k, that is even. But fk = ƒk−1 + fk−2. Applying the induction hypothesis to k − 1 and to k − 2, we conclude that each of ƒk−1 and fk_2 is even, hence, so is the sum. By the Principle of Mathematical Induction, fn is even for all n ≥ 3.