# If $a_{n+1}=a_n+1/a_n$ and $a_0 = 1$, show $a_n/H_n^4\to \infty$ but $a_n/H_n^4\to 0$ [duplicate]

I got interested in the recursion $$a_{n+1} = a_n + \frac1{a_n}$$ in response to a question on this site (which I can no longer locate).

I thought this would be a relatively easy one to solve as an explicit function of $n$. For instance, the closely related recursion $$b_{n+1} = \frac12 \left( b_n + \frac1{b_n} \right)$$ is the sequence of guesses in Newton's algorithm for $\sqrt{1}$, given a starting guess $b_0$, and that turns out to be $$b_{2k} = \tanh\left( 2^{2k} x \right)\\ b_{2k+1} = \frac{1}{ \tanh\left( 2^{2k+1} x \right)}$$ with $x = \tanh^{-1} b_0$.

But the recursion for $a$ is a tougher nut to crack. Although I'd llike to have in in explicit form, that might not be practical (I tried various things, including Jacobi elliptic functions, but I nevery quite get the right identities).

This question asks to prove something about the asymptotic behavior of $a_n$ for the case of arbitrary $a_0>0$, namely that

$$\lim_{n\to\infty} \frac{H_n^4}{a_n} = \lim_{n\to\infty} \frac{a_n} {H_n^5}=0$$ where $H_n$ are the harmonic numbers $$H_n \equiv \sum_{m=1}^n \frac1m$$

## marked as duplicate by Did, JMP, Claude Leibovici, Namaste, TastyRomeoJan 24 '17 at 14:52

• Note: it is easy to see that $a_n\nearrow\infty$, and that $a_n-a_0 = \sum_{k=1}^{n-1}\frac{1}{a_k}$. Not sure what to do from there, though. – Clement C. Jan 24 '17 at 0:02
• Something's up with the limits in your titles: The expressions are identical. – Arthur Jan 24 '17 at 0:03
• If we follow Jack D'Aurizio's idea and put some more effort, we can show that $$a_n^2 = 2n + \frac{1}{2}\log n + c + \mathcal{O}\left( \frac{\log n}{n}\right)$$ for some constant $c$, where both $c$ and the implicit bound for the Big-Oh notation depend on the initial value $a_0$. – Sangchul Lee Jan 24 '17 at 0:14
• – Aryabhata Jan 24 '17 at 0:26

$a_{n+1}^2 = a_{n}^2 + 2 + \frac{1}{a_n^2}$ gives $a_n\geq \sqrt{2n-1}$ as well as $$a_{n+1}^2\leq a_n^2+2+\frac{1}{2n-1}$$ from which $a_n\leq \sqrt{2n+O(\log n)}$.
The given limits are simple to compute given these bounds, but $$\lim_{n\to +\infty}\frac{H_n^4}{a_n} = 0,\qquad \lim_{n\to +\infty}\frac{a_n}{H_n^5}=\color{red}{+\infty}$$ since $H_n=\log(n)+O(1)$.
Thanks to Clement C., here it is a plot of $a_n$ versus $\sqrt{2n}$:
• Not sure how you feel about including empirical confirmation, but if you want to include this (plot of $a_n$ vs. $\sqrt{2n}$ for $0\leq n\leq 100$) in your answer, feel free to: s30.postimg.org/5800t2dy9/an_vs_sqrt2n.png – Clement C. Jan 24 '17 at 0:43