Mathematics for Computer Science

Chapter 2 The Well Ordering Principle32

F.0/WWD0; (2.3)

F.1/WWD1; (2.4)

F.n/WWDF.n1/CF.n2/ forn2: (2.5)

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.

1. The proof is by the WOP.


2. Let Even.n/mean thatF.n/is even.


3. LetCbe the set of counterexamples to the assertion that Even.n/holds for
   alln 2 N, namely,

CWWDfn 2 NjNOT.Even.n//g:

4. We prove by contradiction thatCis empty. So assume thatCis not empty.


5. By WOP, there is a least nonnegative integer,m 2 C,


6. Thenm > 0, sinceF.0/D 0 is an even number.


7. Sincemis the minimum counterexample,F.k/is even for allk < m.


8. In particular,F.m1/andF.m2/are both even.


9. But by the defining equation (2.5),F.m/equals the sumF.m1/CF.m2/
   of two even numbers, and so it is also even.


10. That is, Even.m/is true.


11. This contradicts the condition in the definition ofmthatNOT.Even.m//
    holds.


12. This contradition implies thatCmust be empty. Hence,F.n/is even for all
    n 2 N.