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

is true for all.

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 |$.