4
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 ... ?

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

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.