Math CentralQuandaries & Queries


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.

We have two responses for you


Look closely at P(1).



You require more than one base case since you are referencing both Fn-1 and Fn-2, Snehal.

About Math Central


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
Quandaries & Queries page Home page University of Regina PIMS