SICP exercise 1.13

From Drewiki

Jump to: navigation, search

Problem

Prove that Fib(n) is the closest integer to

$\phi^n/\sqrt{5}$ ,

where

$\phi=(1+\sqrt{5})/2$ .

Hint: Let

$\psi=(1-\sqrt{5})/2$

and use induction and the definition of the Fibonacci numbers to prove that

$Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$ .

Solution

This exercise is off-topic, having little or nothing to do with the subject of the book, but a proof by induction follows. We must show that the equality holds true for n=0 and n=1, and then show that if we assume it's true for n=i, it must also be true for n=i+1.

$F i b (0) = 0$

and

$(\phi^0-\psi^0)/\sqrt{5}=0$

Also:

$F i b (1) = 1$

and

$(\phi-\psi)/\sqrt{5}=\sqrt{5}/\sqrt{5}=1$

Now, by induction, we assume that

$Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$

is true for all n up to and including $n = i + 1$ . We must now show that

$Fib(i+2)=(\phi^{i+2}-\psi^{i+2})/\sqrt{5}.$

We know, by the definition of Fib(n), that

$F i b (i + 2) = F i b (i + 1) + F i b (i)$

Then by substitution:

$Fib(i+2)=(\phi^{i+1}-\psi^{i+1})/\sqrt{5}+(\phi^i-\psi^i)/\sqrt{5} =(\phi^{i+1}+\phi^i-\psi^{i+1}-\psi^i)/\sqrt{5} =(\phi^i(1+\phi)-\psi^i(1+\psi))/\sqrt{5}$