# Asymptotics of a Recursively defined sequence

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?

-

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$).
Thanks, this is helpful. Also, I should note that at least graphically, the inverse of $(a_n)$, (the function that maps $a_n to n$) matches $n/ log (n)$ very closely. –  Alexander Jun 14 '13 at 3:01