# Exercise 1.13

### Proof that \(\text{Fib}(n)\) is the closest integer to \(\varphi^n/\sqrt{5}\).

\(\varphi=\frac{1+\sqrt{5}}{2}\) and \(\psi=\frac{1-\sqrt{5}}{2}\)

Let’s begin to prove by induction that \(\text{Fib}(n)=(\varphi^n - \psi^n)/\sqrt{5}\).

\(\text{P}(n):\quad \text{Fib}(n)=(\varphi^n - \psi^n)/\sqrt{5}\)

**Base case**:

\(\text{P}(n)\) is easily seen to be true for \(n=0\) and \(n=1\):

\(\text{Fib}(0)=0\) by definition and \((\varphi^0 - \psi^0)/\sqrt{5}=0\)

\(\text{Fib}(1)=1\) by definition and \((\varphi^1 - \psi^1)/\sqrt{5}=1\)

**Inductive step**: Show that if \(\text{P}(k)\) and \(\text{P}(k+1)\) holds, then also \(\text{P}(k+2)\) holds. This can be done as follows.

\[\begin{align}\text{Fib}(k+2) & =\text{Fib}(k+1)+\text{Fib}(k)\quad \text{, by definition of the Fibonacci numbers.} \newline & = \frac{\varphi^{k+1} - \psi^{k+1}}{\sqrt{5}}+\frac{\varphi^k - \psi^k}{\sqrt{5}} \newline & = \frac{\varphi^{k+1} + \varphi^k - (\psi^{k+1}+\psi^k)}{\sqrt{5}} \end{align}\]

Since \(\varphi^2=\varphi+1\), we have:

\[\varphi^{k+1}+\varphi^k=\varphi^k(\varphi+1)=\varphi^k\varphi^2=\varphi^{k+2}\] Similary \(\psi^2=\psi+1\), hence:

\[\psi^{k+1}+\psi^k=\psi^k(\psi+1)=\psi^k\psi^2=\psi^{k+2}\]

So we have:

\[\text{Fib}(k+2)=\frac{\varphi^{k+2}-\psi^{k+2}}{\sqrt{5}}\]

Since both the base case and the inductive step have been performed, by mathematical induction the statement \(\text{P}(n)\) holds for all natural numbers \(n\).

As \(\left | \frac{\psi^n}{\sqrt{5}} \right | < \frac{1}{2}\) for \(n\geq 0\), we finally know that \(\text{Fib}(n)\) is the closest integer to \(\varphi^n/\sqrt{5}\). \(\blacksquare\)