Lesson 5

The error in the previous proof is that the statement \(A(n+1)\) is derived from \(A(n)\) and \(A(n-1)\), but the base case is proven only for \(A(6)\). Thus, the step for \(A(7)\) does not work: it requires \(A(5)\) to be proven, which is not only unproven but also incorrect! The original statement however is correct. To correct the proof, the base case must include checking the statement \(A(7)\).

Since the proof is corrected with such a minor adjustment, this error may seem insignificant. In fact, this is a major flaw. If such trivialities are ignored, one could prove a nonsense like “\(F_{n}\) is even, for all \(n \ge 6\)”: \(F_{6}\) is even (base case) and \(F_{n}=F_{n-2}+F_{n-1}\) is even as the sum of even numbers (inductive step).

This is a clear example of the importance of the base case (although in most cases it is easy to check) and that the method of mathematical induction should not be applied too literally: if \(A(n+1)\) relies not only on \(A(n)\) but also on \(A(n-1)\), then the base case needs to be checked for two initial values, not just one. (To extend the domino analogy: suppose the dominoes have such a shape and weight that for one domino to fall, it requires two previous dominoes to fall on it. Then to ensure that all dominoes fall, one needs to push not just the first domino, but the first two.)