Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
"Demonstrating" and "proving" are synonyms. Follow lab bhattacharjee's links and you should be fine. – Hubble May 26 '14 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 '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.

share|cite|improve this answer

$\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} \; $.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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