# How prove this limit $\displaystyle\lim_{n\rightarrow \infty} \frac{f_n}{f_{n+1}}=a$

Let $(f_n)$- real sequence such that $$\lim_{n\rightarrow \infty} \frac{f_{n+1}f_n-f_{n-1}f_{n+2}}{f_{n+1}^2-f_nf_{n+2}}=a+b,$$ and $$\lim_{n\rightarrow \infty} \frac{f_{n}^2-f_{n-1}f_{n+1}}{f_{n+1}^2-f_nf_{n+2}}=ab \quad (|a|<|b|).$$

Prove that:$$\lim_{n\rightarrow \infty} \frac{f_n}{f_{n+1}}=a$$

I think we must prove $\displaystyle\lim_{n\rightarrow \infty} \frac{f_n}{f_{n+1}}$ exists,and we prove this limit is $a$,But I can't prove this limit exists.

My idea: since $$\lim_{n\to\infty}\dfrac{\dfrac{f_{n}}{f_{n+1}}-\dfrac{f_{n-1}}{f_{n}}\dfrac{f_{n}}{f_{n+1}}\dfrac{f_{n+2}}{f_{n+1}}}{1-\dfrac{f_{n}}{f_{n+1}}\dfrac{f_{n+2}}{f_{n+1}}}=a+b$$ and $$\lim_{n\to\infty}\dfrac{\left(\dfrac{f_{n}}{f_{n+1}}\right)^2-\dfrac{f_{n-1}}{f_{n}}\dfrac{f_{n}}{f_{n+1}}}{1-\dfrac{f_{n}}{f_{n+1}}\dfrac{f_{n+2}}{f_{n+1}}}=ab$$ But I felt this deal is not useful,

Other idea: I want to take the Fibonacci sequence to solve this problem, But I can't,

Thank you

This is a supplement to several other answers about existence of the limit.

Let $P_n = \left|\begin{matrix}f_{n+1} & f_{n+2}\\ f_{n-1} & f_n\end{matrix}\right|$ and $Q_n = \left|\begin{matrix}f_{n} & f_{n+1} \\ f_{n-1} & f_n\end{matrix}\right|$, the given condition can be rewritten as

$$\lim_{n\to\infty} \frac{P_n}{Q_{n+1}} = a + b \quad\text{ and }\quad\lim_{n\to\infty} \frac{Q_n}{Q_{n+1}} = ab\tag{*1}$$

Notice $$f_n P_n - f_{n+1}Q_n = f_{n-1} Q_{n+1} \quad\iff\quad f_{n+1} = \frac{P_n}{Q_n} f_n - \frac{Q_{n+1}}{Q_n} f_{n-1}$$ The sequence satisfies a non-linear recurrence relations whose coefficients converge to some finite limit. The "limit" of the recurrence relation has the form

$$f_{n+1} = \left(\frac{1}{a} + \frac{1}{b}\right) f_{n} - \frac{1}{ab} f_{n-1}$$

with characteristic polynomial $\lambda^2 - \left(\frac{1}{a} + \frac{1}{b}\right)\lambda + \frac{1}{ab} = \left(\lambda - \frac{1}{a}\right)\left(\lambda - \frac{1}{b}\right)$.

By assumption, $|a| < |b|$. This means distinct roots of this characteristic polynomial has distinct modulus. By Poincare-Perron theorem$\color{blue}{^{[1]}}$, we have either

• $f_n = 0$ for all sufficiently large $n$ or
• $\lim\limits_{n\to\infty} \frac{f_{n+1}}{f_n}$ exists and equal to $\frac{1}{a}$ or $\frac{1}{b}$.

The assumption $(*1)$ is written in such a way that $Q_{n+1}$ is non-zero for sufficient large $n$. So we can ignore the possibility that $f_n$ vanishes for large $n$. This implies the limit $\lim\limits_{n\to\infty} \frac{f_{n}}{f_{n+1}}$ does exist and equal to either $a$ or $b$.

Notes

• $\color{blue}{[1]}$ For more details of Poincare-Perron theorem and a proof of it, please consult Chapter 8 of Saber Elaydi's book An Introduction to Difference Equations.
• This essentially solves the main problem. As I understand, it also follows from at least some formulation of Poincare-Perron that the limit $1/a$ is the "general limit" while the limit $1/b$ can only occur in "special cases". I've tried to construct such a special case, but failed, and suspect that you might be able to find such a series of $f_n$ which satisfies the recurrence, but that it will not be able to satisfy both of the required limits. – Einar Rødland Mar 1 '14 at 11:04
• And Barry Cipra has already proved that $1/a$ is the limit, not $1/b$. My bad for missing out on that. Thus, the result should be fully proved by the combined effort. – Einar Rødland Mar 1 '14 at 12:20

Sort of useful: let $g_n = \frac{f_n}{f_{n+1}}$, then

$$\lim_{n\to\infty} {g_n \frac{g_{n+1} - g_{n-1}}{g_{n+1} - g_n}} = a+b$$

and

$$\lim_{n\to\infty} {g_n g_{n+1}\frac{g_{n} - g_{n-1}}{g_{n+1} - g_n}} = ab$$

Notice that $\frac{g_{n+1} - g_{n-1}}{g_{n+1} - g_n} = 1 + \frac{g_{n} - g_{n-1}}{g_{n+1} - g_n}$, and letting $h_n = \frac{g_{n} - g_{n-1}}{g_{n+1} - g_n}$, obtain

$$\lim_{n\to\infty} {g_n (1 + h_n)} = a+b$$ and $$\lim_{n\to\infty} {g_n g_{n+1} h_n} = ab$$

Obviously, for $G = \lim_{n\to\infty} {g_n}$ to exist, so must $H = \lim_{n\to\infty} {h_n}$. The rest is simple yet laborous:

• Assume that the limits exist; take them; obtain a quadratic equation for $G$, it will yield $a$ and $b$ as roots (hence candidates for actual limit value).
• Let $\epsilon_n = g_n - r$, where $r$ is the root of the quadratic equation from the previous step, and demonstrate that for lesser root $\epsilon$ diminishes (BTW that completes the proof of existence), while for the larger one it grows.

Note: I've rewritten things to incorporate a considerable simplification pointed out by Einar Rødland.

Here's part of a proof. Let's assume that $\lim_{n\to\infty}f_n/f_{n+1}$ exists, and show that it must equal $a$.

Since $|a|\lt|b|$, we have $b\not=0$, so we can write $f_n/f_{n+1}=bg_n$. (Note: This assumes $f_{n+1}\not=0$, which is justified since we're assuming the limit exists.) We now want to show that $\lim_{n\to\infty}g_n=a/b$. Let's write $r=a/b$. We know that $|r|\lt1$.

In terms of the $g$'s, we have the two limits

$$\lim_{n\to\infty}\left(g_n{g_{n+1}-g_{n-1}\over g_{n+1}-g_n}\right)=1+r$$

and

$$\lim_{n\to\infty}\left(g_ng_{n+1}{g_n-g_{n-1}\over g_{n+1}-g_n}\right)=r$$

Note that we must have $f_{n+1}^2-f_nf_{n+1}\not=0$ for all large $n$, which means that $g_{n+1}-g_n\not=0$ for all large $n$ as well.

The first limit can be rewritten as

$$\lim_{n\to\infty}\left(g_n+{1\over g_{n+1}}\left(g_ng_{n+1}{g_n-g_{n-1}\over g_{n+1}-g_n}\right)\right)=1+r$$

If we now assume that $\lim_{n\to\infty}g_n=G$ (i.e., the limit exists), then we have

$$G+{1\over G}r=1+r$$

which implies $G=1$ or $G=r$. We need to show that $G=1$ leads to a contradiction.

Suppose that $G=\lim_{n\to\infty}g_n=1$. Then

$$\lim_{n\to\infty}\left(g_ng_{n+1}{g_n-g_{n-1}\over g_{n+1}-g_n}\right)=\lim_{n\to\infty}\left({g_n-g_{n-1}\over g_{n+1}-g_n}\right)$$

from which we have

$$\lim_{n\to\infty}\left|g_{n+1}-g_n\over{g_n-g_{n-1}}\right|={1\over |r|}\gt1$$

This implies there is an $N$ such that $g_{N+n}-g_{N+n-1}\not=0$ and

$$\left|g_{N+n+1}-g_{N+n}\over{g_{N+n}-g_{N+n-1}}\right|\gt 1$$

for all $n\ge0$, and this implies

$$\left|g_{N+n}-g_{N+n-1}\over{g_{N}-g_{N-1}}\right|= \left|g_{N+n}-g_{N+n-1}\over{g_{N+n-1}-g_{N+n-2}}\right| \left|g_{N+n-1}-g_{N+n-2}\over{g_{N+n-2}-g_{N+n-3}}\right|\cdots \left|g_{N+1}-g_{N}\over{g_{N}-g_{N-1}}\right|\gt 1$$

for all $n$. But $\lim_{n\to\infty}(g_{N+n}-g_{N+n-1})=0$, and there's our contradiction.

Finally, the answer by achille hui, citing the Poincare-Perron theorem, shows that the limit does exist, so together this settles the OP's question.

• +1 BTW, the limit does exist by Poincare-Perron theorem. – achille hui Feb 27 '14 at 23:56
• It seems to me the formulation could be simplified a bit. Assuming $g_n\rightarrow G$, you get that $|g_n-g_{n-1}|/|g_{n+1}-g_n|\rightarrow |r|/G^2$ (your second limit), and if this limit is less than 1, $|g_{n+1}-g_n|$ will increase for large $n$ and $g_n$ cannot converge. – Einar Rødland Mar 1 '14 at 12:30
• @EinarRødland, thank you! I've rewritten the proof to simplify it. I don't know why I thought it had to be so complicated. – Barry Cipra Mar 1 '14 at 14:59

I'm going to post a failed approach, just so you can see what I tried. This is here only to show an approach and (maybe) generate new ideas.

Let $$x:=a+b\;\;\text{ and }\;\; y:=ab.$$ Assume for now $0<a<b$. Then $$\frac{x-\sqrt{x^2-4y}}{2} =\frac{a+b-\sqrt{(a+b)^2-4ab}}{2} =\frac{a+b-\sqrt{(a-b)^2}}{2} =\frac{a+b-\vert a-b\vert}{2} =\frac{a+b-b+a}{2} =a.$$ Now we replace $a+b$ with $\lim_{n\rightarrow \infty} \frac{f_{n+1}f_n-f_{n-1}f_{n+2}}{f_{n+1}^2-f_nf_{n+2}}$ and $ab$ with $\lim_{n\rightarrow \infty} \frac{f_{n}^2-f_{n-1}f_{n+1}}{f_{n+1}^2-f_nf_{n+2}}$, and due to continuity move the limit outside: $$\frac{a+b-\sqrt{(a+b)^2-4ab}}{2} =\lim_{n\to\infty} \frac{\left(\frac{f_{n+1}f_n-f_{n-1}f_{n+2}}{f_{n+1}^2-f_nf_{n+2}}\right)-\sqrt{\left(\frac{f_{n+1}f_n-f_{n-1}f_{n+2}}{f_{n+1}^2-f_nf_{n+2}}\right)^2 -4\left(\frac{f_{n}^2-f_{n-1}f_{n+1}}{f_{n+1}^2-f_nf_{n+2}}\right)}}{2} =\lim_{n\to\infty} \frac{\left({f_{n+1}f_n-f_{n-1}f_{n+2}}\right) -\sqrt{\left({f_{n+1}f_n-f_{n-1}f_{n+2}}\right)^2 -4\left({f_{n}^2-f_{n-1}f_{n+1}}\right)\left({f_{n+1}^2-f_nf_{n+2}}\right)}}{2\left({f_{n+1}^2-f_nf_{n+2}}\right)} =\lim_{n\to\infty} \frac{f_{n+1}f_n-f_{n-1}f_{n+2} -\sqrt{ f_{n+1}^2f_n^2 -2f_{n+1}f_n f_{n-1}f_{n+2} +f_{n-1}^2f_{n+2}^2 -4f_n^2f_{n+1}^2+4f_{n}^2f_nf_{n+2}+4f_{n-1}f_{n+1}f_{n+1}^2-4f_{n-1}f_{n+1}f_nf_{n+2}} }{2\left({f_{n+1}^2-f_nf_{n+2}}\right)}$$ At this point there are no useful simplifications to be done inside the radical. It does not seem to agree with the $x$ and $y$ case.

I thought this was a counter-example, until reminded that $|a|<|b|$ was required.

For any two numbers $u,v$, let $f_{2k}=u$ and $f_{2k+1}=v$. The expressions in the two limits will then both be constant, with $a+b=0$ and $ab=-1$: real number solutions are $(a,b)=(1,-1)$ and $(-1,1)$. Now, $f_n/f_{n+1}$ will alternate between $u/v$ and $v/u$, and thus not converge (unless $u=\pm v$). However, $|a|=|b|$, so it's not a proper counter-example.

Another attempt I made was to have $f$ loop over values $0,1,-1$, but that would make $a+b=-1$ and $ab=1$ which has no real solutions.

• This is no counter example, because $|a|<|b|$ and thus $a = -b$ is not possible – Stefan Feb 27 '14 at 17:12
• @Stefan: True! I overlooked that requirement. – Einar Rødland Feb 27 '14 at 18:22