# Limit of fibonacci sequence

Let $f_n$ be the $n$th Fibonacci number. Find constants $a$ and $b$ such that

$$\lim_{n\to\infty} \frac{f_n}{a\cdot b^n} = 1$$

I'm somewhat confused on how to approach this problem. I know the closed form of the Fibonnaci sequence, and I think it may have something to do with this problem, but I am unsure of how to proceed. Would love some help!

We can indeed use the closed form of $f_n$. In particular: let $\phi = \frac{1 + \sqrt{5}}{2}$, we have $$\lim_{n \to \infty} \frac{f_n}{ab^n} = \lim_{n \to \infty}(\phi^n - (-1)^n(\phi)^{-n}) \frac{1}{\sqrt{5}ab^n} = \\ \lim_{n \to \infty} [1 - (-1)^n(\phi)^{-2n}] \frac{\phi^{n}}{\sqrt{5}ab^n} =\\ \lim_{n \to \infty} \frac{\phi^{n}}{\sqrt{5}ab^n}$$ Perhaps you could take it from there.

You can use the formula for the Fibonacci numbers $$F_{n}=\left[\frac{\phi^{n}}{\sqrt{5}}\right]$$ to get $$\lim_{n\rightarrow\infty}\frac{F_{n}}{\frac{\phi^{n}}{\sqrt{5}}}=1$$ where $\left[x\right]$ is the integer part of $x$ and $\phi$ is the golden ratio.

HINT: You know that

$$f_n=\frac{\varphi^n-\widehat\varphi^n}{\sqrt5}\;,$$

where $\varphi=\frac12\left(1+\sqrt5\right)$ and $\widehat\varphi=\frac12\left(1-\sqrt5\right)$. Note that $|\widehat\varphi|<1$, so $\widehat\varphi^n\to 0$ as $n\to\infty$. Thus, for large $n$ the Fibonacci number $f_n$ is approximately ... ?

• Would the downvoter care to be useful and explain why (s)he downvoted this answer and not the essentially equivalent later version by Omnomnomnom? – Brian M. Scott Jun 27 '16 at 1:02
• @BrianMScott No accounting for taste, I suppose. I like your answer, though. – Omnomnomnom Jun 27 '16 at 2:23
• @Omnomnomnom: Thanks. I generally tend to favor hints, but yours is a very nice complete answer. – Brian M. Scott Jun 27 '16 at 2:34