# Fibonacci recurrence relations

I came a cross this problem in my regular study of Fibonacci series. Please solve this problem.

Solve the Fibonacci recurrence relation $F_{n+2} = F_{n+1} + F_n$, given $F_0 = 1 = F_1$. Show that $F_n$ grows exponentially, i.e., $F_n$ is of size $r^n$ for some $r > 1$. What is $r$? Let $r_n = F_{n+1}/F_n$. Show that the even terms $r_{2m}$ are increasing and the odd terms $r_{2m+1}$ are decreasing. Investigate $\lim\limits_{n\to \infty} r_n$ for the Fibonacci numbers. Show that $r_n$ converges to the golden mean.

Thanking you, Mahima

-
Please don't ask us to solve problems for you; we can help if you have specific questions and show your work/thought process. –  gary Aug 6 '11 at 6:14
Surely the technique described in answers to your earlier question math.stackexchange.com/q/53710/11619 helps? I mean, if you understood that solution, this is easier (and can also be found in any book on the subject). –  Jyrki Lahtonen Aug 6 '11 at 6:16
Why have you not accepted any of the answers to your previous questions? Some of them seem fine to me; in some cases people put quite a lot of time and effort into them. Please note that the reason for accepting answers is not only to acknowledge the work of those who answered, but also to mark the questions as resolved so that people don't unnecessarily keep coming back to them. –  joriki Aug 6 '11 at 6:22

The specific subparts of your question can be solved most readily once you have a closed form. You can solve this recursion using either power series or what is called the method of annihilation. The power series method is pretty standard, and you should look it up as it is quite useful.

The solution to any linear recurrence is a combination of polynomial and exponential functions in $n$. For the Fibbonacis, you have $F(n) = F(n-1) + F(n-2)$ where where $F(0) = 0$ and $F(1) = 1$. Here is how the annihilator works, consider the shift operator $\hat{O}$ where $\hat{O}^kF(n) = F(n+k)$ then $(\hat{O}^2 -\hat{O}-1)F(n)$ "annihilates" the recursion, (as $F(n+2)-F(n+1)-F(n)=0$). Factor it as $(\hat{O}-\alpha)(\hat{O}-\beta)$.

The operator $\hat{O}-\alpha$ annihiliates geometric sequences, $\{c\alpha^n\}$. Therefore for the Fibonnaci sequences, you have, $$F(n) = a\alpha^n+b\beta^n$$ where $\alpha$ and $\beta$ are the roots of $x^2-x-1=0$. $$F(n)=a\left(\frac{1+\sqrt{5}}{2}\right)^n+b\left(\frac{1-\sqrt{5}}{2}\right)^n$$

The base cases give you two equations in two unknowns. You have $F(0) = 0$ and $F(1)=1$ solve for $a$ and $b$ to get $$F(n)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$$

Finally check it by induction.

-
Thank you so much for your solution. –  MahimA Aug 6 '11 at 8:20
What is r in my question and how will you find the value of r? –  MahimA Aug 6 '11 at 9:29
See p.34 of cs.columbia.edu/~cs4205/files/CM2.pdf also –  Aram Kocharyan Feb 28 '13 at 6:21