# Proving convergence of a recursively defined sequence

Using a computer it is easy to see that the sequences defined by letting $a_1=1$, $a_2=m$, and $$a_n=\frac{2a_{n-1}a_{n-2}}{a_{n-1}+a_{n-2}}$$ converges to $\frac{3m}{m+2}$. I would very much like to know how to prove this. I don't even know where to start.

-

Hint: The following is I think a natural starting "move."

Let $a_n=\dfrac{1}{x_n}$. When the smoke clears you get a nice linear recurrence.

Continuation: Making the suggested substitution, and simplifying, we obtain the recurrence $x_n=\dfrac{1}{2}\left(x_{n-1}+x_{n-2}\right)$. We have to be a little careful, since there will be trouble if $a_{n-1}+a_{n-2}=0$. But for example if $m\gt 0$ then all terms are safely positive.

There are many ways to solve the recurrence. For example we can use a general technique for solving homogeneous linear recurrences with constant coefficients, and write down the characteristic polynomial $2x^2-x-1=0$, which has the roots $1$ and $-\dfrac{1}{2}$.

Thus the general solution of the recurrence is $x_n=A+B\left(-\frac{1}{2}\right)^n$. Putting $x_1=1$ and $x_2=\dfrac{1}{m}$ we find that $A=\dfrac{m+2}{3m}$, and $B=\dfrac{4-2m}{3m}$. Thus $$x_n=\frac{m+2}{3m} + \left(-\frac{1}{2}\right)^n \frac{4-2m}{3m}.$$ As $n\to\infty$, $x_n\to \dfrac{m+2}{3m}$.

Remark: Because the numbers are quite simple, we do not need to use the "general" procedure to solve the recurrence. More generally, consider the recurrence $$y_{n}=py_{n-1}+(1-p)y_{n-2},$$ which comes up in some probability calculations. This may be rewritten as $$y_n-y_{n-1}=(-1)(1-p)(y_{n-1}-y_{n-2}).$$ If we let $z_n=y_{n}-y_{n-1}$, we get $z_n=(-1)(1-p)z_{n-1}$. So the sequence $(z_n)$ is a geometric sequence with common ratio $-(1-p)$. Now we can easily find a general expression for $z_n$, and hence for $y_n$.

-
I don't follow. What is $x_n$? –  Carolus Nov 2 '12 at 15:02
Whatever the sequence $(a_n)$ is, let $(x_n)$ be the sequence of its reciprocals. The sequence $(x_n)$ is a lot nicer. Just plug in $1/x_k$ everywhere you see $a_k$, and simplify. –  André Nicolas Nov 2 '12 at 15:04
Thank you for only giving me a hint at first. It was a good exercise! –  Carolus Nov 3 '12 at 8:11

Let $A_n=\frac{a_n}{a_{n-1}}$, then we have $A_n=\frac{2}{1+A_{n-1}}$, it is easy to find that $\lim\limits_{n\to\infty }A_n$ exists then we have $\lim\limits_{n\to\infty }\frac{a_n}{a_{n-1}}=\frac{\sqrt{2}-1}{2}<1$, we can use the $\epsilon- N$ to illustrate the result......

-
This shows that $A_n\to1$. And? –  Did Nov 2 '12 at 16:16