**Exercise 1.13:** Prove that `Fib(n)`

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

$$ F_n = F_{n-1} + F_{n-2} $$

$$ F_0 = 0 $$

$$ F_1 = 1 $$

Fn is a linear second-order recurrence with constant coefficients. The characteristic equation for it is: $$ r^2-r-1=0 $$

$$ r = \phi , \psi $$

This means that the closed form solution is of the form \( F_n = \alpha\phi^n-\beta\psi^n \) The constants \( \alpha \) and \( \beta \) are determined by the initial conditions bellow.

$$ F_0 = \alpha + \beta = 0 $$

$$ \alpha = -\beta $$

$$ F_1 = \alpha\phi + \beta\psi = 1 $$

$$ \beta(\psi-\phi)=1 $$

$$ \beta=\frac{1}{\psi-\phi} $$

$$ \alpha=\frac{-1}{\psi-\phi} $$

The closed expression has the following form:

$$ F_n = \frac{-\phi^n}{\psi-\phi}-\frac{\psi^n}{\psi-\phi}=\frac{\phi^n-\psi^n}{\sqrt5} $$

Now that the derivation of the closed form for Fn is done here’s the proof by induction.

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

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

$$ F_n = \frac{\phi^n-\psi^n}{\sqrt5} $$

$$ F_0 = \frac{\phi^0-\psi^0}{\sqrt5}=0 $$

$$ F_1 = \frac{\phi^1-\psi^1}{\sqrt5}=1 $$

Perform the induction step:

Assume: \( F_n = \frac{\phi^n-\psi^n}{\sqrt5} \)

$$ F_{n+1} = F_{n}+F_{n-1} = \frac{\phi^n-\psi^n}{\sqrt5} + \frac{\phi^{n-1}-\psi^{n-1}}{\sqrt5}=\frac{\phi^{n+1}-\psi^{n+1}}{\sqrt5} $$

$$ F_{n+1} = \frac{\phi^{n-1}(\phi+1)-\psi^{n-1}(\psi+1)}{\sqrt5} $$

Because \( \phi^2 = \phi+1 \)

$$ F_{n+1} = \frac{\phi^{n-1}(\phi+1)-\psi^{n-1}(\psi+1)}{\sqrt5}=\frac{\phi^{n+1}-\psi^{n+1}}{\sqrt5} $$

The proof that \( F_n = \frac{\phi^n}{\sqrt5} \) is straightforward.

$$ \psi = \frac{1-\sqrt{5}}{2} = -0.618 $$

\( \lim_{n \to \infty}\psi^n = 0 \) for example \( \psi^{30} \approx 0.0000005374904998555718 \) and \( \phi^{30} \approx 1860498$ \)

$$ \epsilon = 1-\frac{\phi^{30}-\psi^{30}}{\phi^{30}} \approx 2.8899105330992825 \cdot 10^{-13} $$

Clearly for n>30 \( F_n = \frac{\phi^n}{\sqrt5} \) is a good approximation.