Mathematics for Computer Science

Chapter 5 Induction156

Class Problems

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

FnWWD

8

ˆ<

ˆ:

0 ifnD0;

1 ifnD1;

Fn 1 CFn 2 ifn > 1:

Prove, using strong induction, the following closed-form formula forFn.^8

FnD

pnqn

p

5

wherepD^1 C

p

5

2 andqD

1
p
5
2.
Hint:Note thatpandqare the roots ofx^2 x 1 D 0 , and sop^2 DpC 1 and
q^2 DqC 1.

Problem 5.22.
A sequence of numbers isweakly decreasingwhen each number in the sequence is
the numbers after it. (This implies that a sequence of just one number is weakly
decreasing.)
Here’s a bogus proof of a very important true fact, every integer greater than 1 is
aproduct of a unique weakly decreasing sequence of primes—a pusp, for short.
Explain what’s bogus about the proof.

Lemma.Every integer greater than 1 is a pusp.

For example, 252 D 7
3
3
2
2 , and no other weakly decreasing sequence of
primes will have a product equal to 252.

Bogus proof.We will prove the lemma by strong induction, letting the induction
hypothesis,P.n/, be
nis a pusp:

So the lemma will follow if we prove thatP.n/holds for alln 2.

Base Case(nD 2 ): P.2/is true because 2 is prime, and so it is a length one
product of primes, and this is obviously the only sequence of primes whose product
can equal 2.

(^8) This mind-boggling formula is known asBinet’s formula. We’ll explain in Chapter 15, and again
in Chapter 21, how it comes about.