Question from snehal, a student:

Find the problem in the following argument. Try to give another example that illustrates the same problem.
Claim: All Fibonacci numbers are even.
Proof: We will 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.