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
