Mathematics for Computer Science

Chapter 5 Induction154

False Claim.Every Fibonacci number is even.

False proof. 1. We use strong induction.

2. The induction hypothesis is thatF.n/is even.


3. We will first show that this hypothesis holds fornD 0.


4. This is true, sinceF.0/D 0 , which is an even number.


5. Now, supposen 2. We will show thatF.n/is even, assuming thatF.k/is
   even for allk < n.


6. By assumption, bothF.n1/andF.n2/are even.


7. Therefore,F.n/is even, sinceF.n/DF.n1/CF.n2/and the sum of
   two even numbers is even.


8. Thus, the strong induction principle implies thatF.n/is even for alln > 0.
   

Problem 5.19.
ThenthFibonacci number,F.n/, is defined as follows

F.0/WWD0; (5.19)

F.1/WWD1; (5.20)

F.n/WWDF.n1/CF.n2/ forn > 1: (5.21)

Indicate exactly which sentence(s) in the following bogus proof contain logical
errors? Explain.

False Claim.Every Fibonacci number is even.

Bogus proof.Let all the variablesn;m;kmentioned below be nonnegative integer
valued. Let Even.n/mean thatF.n/is even. The proof is by strong induction with
induction hypothesis Even.n/.

base case:F.0/D 0 is an even number, so Even.0/is true.

inductive step: We assume may assume the strong induction hypothesis

Even.k/for 0 kn;

and we must prove Even.nC1/.