# 1.13

## Exercise 1.13: Prove that Fib(n) is the closest integer to $\frac{\phi ^ n}{\sqrt 5}$, where $\phi=\frac{1+\sqrt 5}{2}$. Hint: Let $\psi = \frac{1-\sqrt 5}{2}$. Use induction and the definition of the Fibonacci numbers (see 1.2.2) to prove that $Fib(n)=\frac{\phi^n - \psi^n}{5}$.

First of all, we know the following two equations are true:

$Fib(0) = 0 = \frac{\phi^0-\psi^0}{\sqrt{5}} = \frac{1-1}{\sqrt 5}$

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

Then we suppose that $Fib(n) = \frac{\phi^n - \psi^n}{\sqrt 5}$ is true for all $n\ge2$.

And from the definition of Fibonacci numbers we have the following:

$Fib(n+1) = Fib(n) + Fib(n-1) = \frac{\phi^n - \psi^n}{\sqrt 5} + \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt 5}$

$= \frac{(\phi^n + \phi^{n-1}) - (\psi^n + \psi^{n-1})}{\sqrt 5}$

Now the only question is if the following equations are true?

$\phi^{n+1} = \phi^n + \phi^{n-1}$

$\psi^{n+1} = \psi^n + \psi^{n-1}$

If the above equations are true, then the previous equations can be deducted into:

$Fib(n+1)=Fib(n)+Fib(n-1) = \frac{\phi^{n+1} + \psi^{n+1}}{\sqrt 5}$

So the equation $Fib(n) = \frac{\phi^n - \psi^n}{\sqrt 5}$ is true for all $n\ge0$.

And

$\mid \frac{\phi^n}{\sqrt 5} - Fib(n) \mid = \mid \frac{\phi^n}{\sqrt 5} - \frac{\phi^n - \psi^n}{\sqrt 5} \mid = \mid \frac{\psi^n}{\sqrt 5} \mid = \mid \frac{(\frac{1-\sqrt 5}{2})^n}{\sqrt 5} \mid \le \mid \frac{\frac{1-\sqrt 5}{2}}{\sqrt 5} \mid = \frac{\sqrt 5 - 1}{2\sqrt 5} = \frac{1-\frac{1}{\sqrt5}}{2}$

$= \frac{1}{2} - \frac{1}{2\sqrt 5} < \frac{1}{2}$

So $Fib(n)$ is the closest integer to $\frac{\phi^n}{\sqrt 5}$.

Now let's examine the previous question: are the following equations true?

$\phi^{n+1} = \phi^n + \phi^{n-1}$

$\psi^{n+1} = \psi^n + \psi^{n-1}$

We firstly examine the equations for $n=0$:

$\phi^0 = 1$

then for $n=1$:

$\phi^1 = \frac{1+\sqrt 5}{2}$

and then for $n = 2$:

$\phi^2 = (\frac{1 + \sqrt 5}{2})^2 = \frac{1 + 5 + 2\sqrt 5}{4} = \frac{3 + \sqrt 5}{2} = 1 + \frac{1+\sqrt 5}{2} = \phi^0 + \phi^1$

Suppose for all $n \ge 2$, we have $\phi^n = \phi^{n-1} + \phi^{n-2}$, then

$\phi^{n+1} = \phi^n \phi = (\phi^{n-1} + \phi^{n-2}) \phi = \phi^n + \phi^{n-1}$

So indeed that $\phi^{n+1} = \phi^{n} + \phi^{n-1}$.

Now let's see if $\psi^{n+1} = \psi^{n} + \psi^{n-1}$ is true.

Since $\psi^0 = 1$ and $\psi^1 = \frac{1-\sqrt 5}{2}$, and

$\psi^{2} = (\frac{1-\sqrt 5}{2})^2 = \frac{1+5-2\sqrt 5}{2} = \frac{3-\sqrt 5}{2} = 1 + \frac{1 - \sqrt 5}{2} = \psi^0 + \psi^1$

Suppose for all $n \ge 2$, $\psi^n = \psi^{n-1} + \psi^{n-2}$, then

$\psi^{n+1} = \psi\psi^n=\psi(\psi^{n-1} + \psi^{n-2})=\psi^n+\psi^{n-1}$

So indeed, $\psi^{n+1}=\psi^n+\psi^{n-1}$ is true for all $n \ge 0$.