# Is Every Fibonacci number is even…? -Maths for Computer science

The Fibonacci numbers F(0), F(1), F(2)… are defined as follows:

Exactly which sentence(s) in the following bogus proof contain logical errors?

Explain.

False Claim. Every Fibonacci number is even.

2.4. Well Ordered Sets 37

Bogus proof. Let all the variables n;m; k mentioned below be nonnegative integer

valued.

1. The proof is by the WOP.

2. Let EF(n) mean that F(n)is even.

3. Let C be the set of counterexamples to the assertion that EF(n) holds for all

n (belong to) N,

4. We prove by contradiction that C is empty. So assume that C is not empty.

5. By WOP, there is a least nonnegative integer m (belongs to)C.

6. Then m > 0, since F(0) =0 is an even number.

7. Since m is the minimum counterexample, F(k) is even for all k < m.

8. In particular, F(m-1) and F.(m-2) are both even.

9. But by the definition, F(m) equals the sum F(m-1) + F(m-2) of two

even numbers, and so it is also even.

10. That is, EF(m) is true.

11. This contradicts the condition in the definition of m that NOT.EF(m)holds.

12. This contradition implies that C must be empty. Hence, F(n) is even for all

n 2 N.

source -“mcs” — 2017/6/5–19:42 — page 37 — #45

https://courses.csail.mit.edu/6.042/spring17/mcs.pdf

Programmer | Technical content Writer | Lives in India | Wanna go where I can breathe freedom

## More from Kirtipurohit

Programmer | Technical content Writer | Lives in India | Wanna go where I can breathe freedom