Asymptotics of a Recursively defined sequence

Question

Suppose we define the sequence $a_n$ recursively by $p_1=1/2, a_1=2$, $p_{n+1}=p_n-\frac{{p_n}^2}{a_np_n+1}, a_{n+1}=a_n+\frac{1}{p_n}$. How does $(a_n)$ behave for large $n$? For instance, what is a function $f(n)$ satisfying $\lim\limits_{n \to \infty} \frac{f(n)}{a_n}=1$? How does one go about solving such a problem?

Answer 1

One can rewrite the recursive formula for $p$ as $p_{n+1}=p_n(1-1/a_{n+1})$.

So, as long as $p_n>0$, $a_n$ is increasing, and, as long as $a_n>1$, $p_n>0$. Since $p_1>0$ and $a_1>1$, by induction we see that both are positive, $p_n$ is decreasing, and $a_n$ is increasing.

If $p_n>p>0$, then $a_n$ grows asymptotically linearly, and $\prod(1-\frac{1}{a_n})=0$ - a contradiction. Thus $p_n\rightarrow 0$ and $a_n\rightarrow+\infty$.

Since $p_n=\prod(1-\frac{1}{a_n})\rightarrow 0$, we see that $\sum\frac{1}{a_n}$ diverges (thus $a_n$ cannot grow much faster than linearithmic $n\log n$).