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.

Proof statement

I may misunderstand the statement itself, although I was able to show for e.g, that Fib(3) was closer to $\Large{\frac{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.

  • 1
    $\begingroup$ "Demonstrating" and "proving" are synonyms. Follow lab bhattacharjee's links and you should be fine. $\endgroup$ – Hubble May 26 '14 at 16:23
  • 3
    $\begingroup$ 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$. $\endgroup$ – Mike May 26 '14 at 16:32

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:


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.


$\phi^n = F_{n-1} + F_n \phi$, and $ \psi^n = F_{n-1} + F_n \psi$. Therefore, $$F_n = \frac{1}{\sqrt{5}} \phi^n - \frac{1}{\sqrt{5}} \psi^n$$.

$-1< \psi <0$ and $2< \sqrt{5} <3$, therefore $0 < | \frac{1}{\sqrt{5}} \psi^n | <\frac{1}{2}$

Let's assume, there is integer $A$, which closer to $\frac{1}{\sqrt{5}} \phi^n$ than $F_n$, and $A = \frac{1}{\sqrt{5}} \phi^n - \alpha$, where $0 < | \alpha | < | \frac{1}{\sqrt{5}} \psi^n |$.

Therefore, $A - F_n = \frac{1}{\sqrt{5}} \psi^n - \alpha$ should also be integer.

But, because of $0< | \alpha | < | \frac{1}{\sqrt{5}} \psi^n | < \frac{1}{2}$, the difference $\frac{1}{\sqrt{5}} \psi^n - \alpha$ cannot be integer. (Further explanation may be needed.....)

So, $ \; \LARGE{F_n} \;$ is the closest integer to $ \; \; \LARGE{\frac{1}{\sqrt{5}} \phi^n} \; $.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.