sol-1.13.tex

\def\Fib{\mathop{\rm Fib}\nolimits}%
In order to show that $\Fib(n) = (\phi^n - \psi^n)/\sqrt5$, we first show that the relation holds for $n=0$ and $n=1$,
$$
\eqalign{
  \Fib(0) &= {\phi^0 - \psi^0 \over \sqrt5} = {1 - 1 \over \sqrt5} = 0 \cr
  \Fib(1) &= {\phi^1 - \psi^1 \over \sqrt5} = {{1 + \sqrt5 \over 2} - {1 - \sqrt5 \over 2} \over \sqrt5} = 1\hbox{,} \cr
}
$$
and then, assuming by induction that it holds for $n-2$ and $n-1$, we show that it holds also for $n$,
$$
\eqalign{
\Fib(n) &= \Fib(n-2) + \Fib(n-1) \cr 
        &= {\phi^{n-2} - \psi^{n-2} \over \sqrt5} + {\phi^{n-1} - \psi^{n-1} \over \sqrt5} \cr 
        &= {\phi^{n-2}(1+\phi) + \psi^{n-2}(1+\psi) \over \sqrt5} \cr 
        &= {\phi^n + \psi^n \over \sqrt5} = \Fib(n)\hbox{.} \cr
}
$$
Finally, we can prove that $\Fib(n)$ is the closest integer to $\phi^n / \sqrt5$ simply by noticing that
$$
\Fib(n) = {\phi^n - \psi^n \over \sqrt5} = {\phi^n \over \sqrt5} - {\psi^n \over \sqrt5}
$$
and that $\psi^n / \sqrt5 < 1/2$ for each $n$.