Take the 2-minute tour ×
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.

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 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|improve this question
    
1  
"Demonstrating" and "proving" are synonyms. Follow lab bhattacharjee's links and you should be fine. –  iHubble May 26 at 16:23
3  
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
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

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.