Mathematics for Computer Science

Chapter 2 The Well Ordering Principle34

So supposeS.m10/holds. Then 5 j.m10/, because...

But if 5 j.m10/, then obviously 5 jm, contradicting the fact thatm

is a counterexample.

Next, ifS.m15/holds, we arrive at a contradiction in the same way.

Since we get a contradiction in both cases, we conclude that...

which proves that (2.2) holds.

Problem 2.2.
TheFibonacci numbersF.0/;F.1/;F.2/;:::are defined as follows:

F.0/WWD0;

F.1/WWD1;

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

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.