# Help with a proof involving Fibonacci numbers.

I'm working through SICP MIT course, and I'm a little lost on how to prove the following statement. I think I'm able to demonstrate it, but have no idea how to prove this statement.

I may misunderstand the statement itself, although I was able to show for e.g, that Fib(3) was closer to a^3/(sqrt 5) than Fib(2), or Fib (4).

With regards to the hint, I'm not sure where this comes into play, although I can already see that it belongs to the Fibonacci formula.

This is the first part of the rest, which is an inductive proof of the Fibonacci sequence (which I know how has been a recurring question).

Any help would be a appreciated.

-
"Demonstrating" and "proving" are synonyms. Follow lab bhattacharjee's links and you should be fine. –  iHubble May 26 at 16:23
Are you allowed to use that $F_n$ is an integer equal to $\frac{\phi^n}{\sqrt5}-\frac{\psi^n}{\sqrt5}$? If so, I imagine you could simply prove that the absolute value of the second term is less than $\frac12$. –  Mike May 26 at 16:32

## 1 Answer

Seeing the form of the solution should lead you to explore how Fibonacci numbers can be represented by an exponential law.

Try $F_n=t^n$ as a possible solution and inject that in the definition by recurrence:

$$F_n=t^n=F_{n-1}+F_{n-2}=t^{n-1}+t^{n-2}.$$

Simplifying by $t^{n-2}$, you get:

$$t^2=t+1,$$ giving two different solutions, namely $\phi^n$ and $\psi^n$, corresponding to the roots $t=\phi$ and $t=\psi$ of this second degree equation.

But you are not done yet, as none of these exponentials satisfy the initial conditions $F_0=F_1=1$.

You now have to observe that the recurrence equation is linear, meaning that any linear combination of solutions is also a solution: $$\phi^n=\phi^{n-1}+\phi^{n-2}\land\psi^n=\psi^{n-1}+\psi^{n-2}\implies a\phi^n+b\psi^n=a\phi^{n-1}+b\psi^{n-1}+a\phi^{n-2}+b\psi^{n-2}$$

It remains to determine $a$ and $b$, from: \begin{align}F_0=a\phi^0+b\psi^0&=1\\ F_1=a\phi^1+b\psi^1&=1.\end{align}

Lastly, you will check why the $\psi^n$ term can be replaced by the rounding of the $\phi^n$ term.

-