Mathematics for Computer Science

Chapter 6 Induction156

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/.
So assumenC 1  2. Then by strong induction hypothesis, Even.n/and
Even.n1/are true, that is,F.n/andF.n1/are both even. But by the defining
equation (6.16),F.nC1/equals the sum,F.n/CF.n1/, of two even numbers,
and so it is also even. This proves Even.nC1/as required.
Hence,F.m/is even for allm 2 Nby the Strong Induction Principle.


Problem 6.26.
Prove that the fast exponentiation state machine of Section 6.2.5 will halt after

dlog 2 neC 1 (6.17)

transitions starting from any state where the value ofzisn 2 integersC.
Hint:Strong induction.

Problem 6.27.
The binary-GCD state machine computes the GCD ofaandbusing only division
by 2 and subtraction, which makes it run very efficiently on hardware that uses bi-
nary representation of numbers. In practice, it runs more quickly that the Euclidean
algorithm state machine (8.3).