Prove that $Fib(n)$ is the closest integer to $\phi^n/5$, where $\phi = (1+\sqrt{5})/2$.
Hint: Let $\psi = (1 - \sqrt{5})/2$. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that $Fib(n) = (\phi^n - \psi^n)/\sqrt{5}$.
Let's represent the number of steps $S$ required to compute the Fibonacci sequence as a recurrence relation:
$$S_n = S_{n-1} + S_{n-2}$$
Let's assume
$$S_n = (\phi^n - \psi^n)/\sqrt{5}$$
such that
- $\psi = (1 - \sqrt{5}) / 2$
-
$\phi = (1 + \sqrt{5}) / 2$.
If we can show $S_{n+1} = (\phi^{n+1} - \psi^{n+1})/\sqrt{5}$ follows our definition of $S_n$, we are done.
$$
S_{n+1} = S_{n} + S_{n-1} \[10pt]
S_{n+1} = (\phi^{n} - \psi^{n})/\sqrt{5} + (\phi^{n-1} - \psi^{n-1})/\sqrt{5} \[10pt]
S_{n+1} = (\phi^{n} - \psi^{n} + \phi^{n-1} - \psi^{n-1})/\sqrt{5} \[10pt]
S_{n+1} = (\frac{\phi^{n+1}}{\phi} - \frac{\psi^{n+1}}{\psi} + \frac{\phi^{n+1}}{\phi^2} - \frac{\psi^{n+1}}{\psi^2})/\sqrt{5} \[10pt]
S_{n+1} = ((\frac{\phi^{n+1}}{\phi} + \frac{\phi^{n+1}}{\phi^2}) - (\frac{\psi^{n+1}}{\psi} + \frac{\psi^{n+1}}{\psi^2}))/\sqrt{5} \[10pt]
S_{n+1} = (\phi^{n+1} (\frac{1}{\phi} + \frac{1}{\phi^2}) - \psi^{n+1} (\frac{1}{\psi} + \frac{1}{\psi^2}))/\sqrt{5} \[10pt]
S_{n+1} = (\phi^{n+1} (\frac{2}{1 + \sqrt{5}} + \frac{4}{(1 + \sqrt{5})^2}) - \psi^{n+1} (\frac{2}{1 - \sqrt{5}} + \frac{4}{(1 - \sqrt{5})^2}))/\sqrt{5} \[10pt]
S_{n+1} = (\phi^{n+1} \frac{6 + 2 \sqrt{5}}{(1 + \sqrt{5})^2} - \psi^{n+1} \frac{6 - 2 \sqrt{5}}{(1 - \sqrt{5})^2})/\sqrt{5} \[10pt]
S_{n+1} = (\phi^{n+1} \frac{6 + 2 \sqrt{5}}{1 + 2 \sqrt{5} + 5} - \psi^{n+1} \frac{6 - 2 \sqrt{5}}{1 - 2 \sqrt{5} + 5})/\sqrt{5} \[10pt]
S_{n+1} = (\phi^{n+1} - \psi^{n+1})/\sqrt{5}.\mkern5mm _\square
$$