1.8 Induction | 1.8 Induction | Unit 1: Proofs | Mathematics for Computer Science | Electrical Engineering and Computer Science

A Bogus Induction

The Fibonacci numbers

\(0, 1, 1, 2, 3, 5, 8, 13, \ldots \)

are defined as follows: let \(F(n)\) be the \(n^{th}\) Fibonacci number,

\(F(0) ::= 0\)
\(F(1) ::= 1\)
\(F(n) ::= F(n-1) + F(n-2), \;\; \text{ for } n \ge 2 \)

Bogus Claim: Every Fibonacci number is even.

Which step(s) in the proof contain logical errors?

Proof by strong induction.

Induction hypothesis: \(F(n)\) is even.

Base case: \(F(0) = 0\), which is an even number.

Induction step: suppose \(n \geq 2\), we assume \(F(k)\) is even for all \(k < n\).

By assumption, both \(F(n-1)\) and \(F(n-2)\) are even.

Therefore, \(F(n)\) is even, since \(F(n) = F(n-1) + F(n-2)\) and the sum of two even numbers is even.

Conclusion: the strong induction principle implies that \(F(n)\) is even for all \(n > 0.\;\;\;\blacksquare\)

Lines 1 through 6 contain no logical errors. The fatal flaw is in line 7. Using strong induction, we can conclude that a predicate \(P(n)\) holds for all \(n \geq 0\) provided that we show all of the following:

\(P(0)\)
\( P(0) \to P(1) \)
\([P(0) \wedge P(1)] \to P(2)\)
\([P(0) \wedge P(1) \wedge P(2)] \to P(3)\)
etc.

The first assertion is proved in line 3. The third and subsequent assertions are proved on lines 4-6. However, the second assertion, \(P(0) \to P(1)\), is proved nowhere (and is actually false). Therefore, we cannot apply the strong induction principle in line 7.

If you said that line 4 contains a logical error, you were on the right track. The natural place to prove the second assertion would have been in line 4. But by saying, "suppose \(n \geq 2\)" instead of "suppose \(n \geq 1\)", the proof explicitly avoided doing so.

Technically, there is no logical error in line 4: It is simply the beginning of a proof for the case when \(n \geq 2\). On the other hand, it's reasonable to say that line 4 is the place where the proof makes a strategic error because it skips the \(n = 1\) case.