Mathematics for Computer Science

Chapter 5 Induction158

thenpjxifor some 1 in.

Bogus proof.Proof by strong induction onn. The induction hypothesis,P.n/, is
that Lemma holds forn.
Base casenD 1 : WhennD 1 , we havepjx 1 , therefore we can letiD 1 and
concludepjxi.
Induction step: Now assuming the claim holds for allkn, we must prove it
fornC 1.
So supposepjx 1 x 2


xnC 1. LetynDxnxnC 1 , sox 1 x 2


xnC 1 Dx 1 x 2


xn 1 yn.
Since the righthand side of this equality is a product ofnterms, we have by induc-
tion thatpdivides one of them. Ifpjxifor somei < n, then we have the desired
i. Otherwisepjyn. But sinceynis a product of the two termsxn;xnC 1 , we have
by strong induction thatpdivides one of them. So in this casepjxiforiDnor
iDnC 1. 

Exam Problems

Problem 5.26.
The Fibonacci numbersF 0 ;F 1 ;F 2 ;:::are defined as follows:

FnWWD

8

ˆ<

ˆ:

0 ifnD0;

1 ifnD1;

Fn 1 CFn 2 ifn > 1:

These numbers satisfy many unexpected identities, such as

F 02 CF 12 C


CFn^2 DFnFnC 1 (5.22)

Equation (5.22) can be proved to hold for alln 2 Nby induction, using the equation
itself as the induction hypothesis,P.n/.

(a)Prove the

base case.nD0/.

(b)Now prove the

inductive step.

Problem 5.27.
Use strong induction to prove thatn 3 n=3for every integern 0.