4
$\begingroup$

This question already has an answer here:

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$$

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – Clement C. Jan 24 '17 at 0:02
  • 2
    $\begingroup$ Something's up with the limits in your titles: The expressions are identical. $\endgroup$ – Arthur Jan 24 '17 at 0:03
  • $\begingroup$ 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$. $\endgroup$ – Sangchul Lee Jan 24 '17 at 0:14
  • $\begingroup$ Related: math.stackexchange.com/questions/29777/… $\endgroup$ – Aryabhata Jan 24 '17 at 0:26
6
$\begingroup$

$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}$:

enter image description here

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – Clement C. Jan 24 '17 at 0:43
  • $\begingroup$ @ClementC.: many thanks, where may I give a (+1) for the contribute? $\endgroup$ – Jack D'Aurizio Jan 24 '17 at 0:49
  • $\begingroup$ Nowhere needed -- I had made a plot, might as well not let it be wasted. $\endgroup$ – Clement C. Jan 24 '17 at 0:50
  • $\begingroup$ @Clement C. How do you get this result by evaluation \sqrt{2n}, I don't very understand, so I posted my questions here:math.stackexchange.com/questions/2128325/… $\endgroup$ – Mclalalala Feb 5 '17 at 6:33
  • $\begingroup$ Thank you for giving me an answer $\endgroup$ – Mclalalala Feb 5 '17 at 6:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.