What is the asymptotic expansion of $x_n$ where $x_{n+1} = x_n+1/x_n$? Let
$x_{n+1} = x_n+1/x_n,
x_0 = a \gt 0$
and
$y_n = x_n^2$.
What is the asymptotic expansion
of $x_n$ ($y_n$ will do)?
I can show that
$y_n
=2n+\dfrac12 \ln(n) + O(1)
$.
Is there an explicit form
for the constant
implied by the $O(1)$?
What is the asymptotic form
of the terms following that constant
(e.g.,
$O(\frac{\ln(n)}{n}),
O(\frac1{n}), ...
$)?
 A: Not a complete answer. Let me first reproduce what I imagine is your argument. We have $y_{n+1} = y_n + \frac{1}{y_n} + 2$. In particular $y_{n+1} \ge y_n + 2$ which gives $y_n \ge 2n + a^2$ and hence $\frac{1}{y_n} \le \frac{1}{2n + a^2}$. This gives
$$y_{n+1} \le y_n + 2 + \frac{1}{2n + a^2}$$
which gives
$$y_n \le 2n + \sum_{i=0}^{n-1} \frac{1}{2i + a^2} + a^2 = 2n + \frac{1}{2} \log n + C$$
for some constant $C$. Write $y_n = 2n + \frac{1}{2} H_{n-1} + e_n$, where we now know that $e_n$ is bounded from above by a constant (and it's not hard to show that it's bounded from below by a constant also). Then the recurrence relation gives
$$y_{n+1} - y_n = 2 + \frac{1}{2n} + e_{n+1} - e_n = \frac{1}{2n + \frac{1}{2} H_{n-1} + e_n} + 2$$
and rearranging a bit gives
$$e_n - e_{n+1} = \frac{1}{2n} - \frac{1}{2n + \frac{1}{2} H_{n-1} + e_n} = \frac{ \frac{1}{2} H_{n-1} + e_n}{2n \left( 2n + \frac{1}{2} H_{n-1}+ e_n) \right)}.$$
Heuristically this gives something like $e_n = C + \frac{\ln n}{8n} + \dots$ but I don't know how to prove it off the top of my head, mostly because I can't think of a reasonable way to describe the constant $C$.
A: Not a rigorous answer, and it is rather a continuation of Mr Cohen's work.
My idea
My idea is standard, I just try to put all the approximate terms aside to see what will be left.
Main work
We start by giving the following equation.
$y_{n+1}-2(n+1)-\frac{1}{2}\ln(n+1) = -\frac{\ln(n)}{4ny_n}+\frac{\frac{1}{2}\ln(n) +2n-y_n}{2ny_{n}}-\frac{1}{2}\left[ \ln(1+\frac{1}{n}) -\frac{1}{n}\right]+( y_{n}-2n-\frac{1}{2}\ln(n))$
So if the approximation given by Mr Cohen is true, we have:
$$|e_{n+1}-e_n|=\left| -\frac{\ln(n)}{4ny_n}+\frac{\frac{1}{2}\ln(n) +2n-y_n}{2ny_{n}}-\frac{1}{2}\left[ \ln(1+\frac{1}{n}) -\frac{1}{n}\right]\right| \le c_1\frac{ln(n)}{n^2} $$
for some constant $c_1>0$, where $e_n:= y_n-2n-\frac{1}{2}\ln(n)$ as in the post of Mr Qiaochu.
Hence, $e_{n}$ converges to some limit, noted by $C$ also as in the post of Mr Qiaochu
Let  $u_n:=e_n-C$
then, the very fist equation is equivalent to
$$u_{n+1}-u_n= \frac{-u_n}{2ny_n}-\frac{\ln(n)}{4ny_n}-\frac{C}{2ny_n}-\frac{1}{2}\left[ \ln(1+\frac{1}{n})-\frac{1}{n} \right]$$
Thus,
$$-u_N = \sum_{n \ge N}\left\{ \frac{-u_n}{2ny_n}-\frac{\ln(n)}{4ny_n}-\frac{C}{2ny_n}-\frac{1}{2}\left[ \ln(1+\frac{1}{n})-\frac{1}{n} \right] \right\}$$
Clearly,
$$ \lim_{N \rightarrow +\infty} \frac{N}{\ln(N)}\sum_{n \ge N}\frac{-u_n}{2ny_n}=0$$
$$\lim_{N \rightarrow +\infty} \frac{N}{\ln(N)}\sum_{n \ge N}\frac{C}{2ny_n}=0$$
$$\lim_{N \rightarrow +\infty} \frac{N}{\ln(N)}\sum_{n \ge N}\left[ \ln(1+\frac{1}{n})-\frac{1}{n}\right]=0$$
And though it is not really straightforward, it is also not hard to see that:
$$\lim_{N \rightarrow +\infty} \frac{N}{\ln(N)}\sum_{n \ge N}\frac{\ln(n)}{4ny_n} = \dfrac{1}{8}$$
So, in conclusion
$$y_n= 2n+\frac{1}{2}\ln(n)+C+\frac{1}{8}\frac{\ln(n)}{n}+o(\frac{\ln(n)}{n}) $$
Comment: It looks like the next terms are $\frac{1}{n}$ something and  $\frac{\ln(n)^2}{n^2}$ something. So, it would be a surprise to me if one can find an analytic form for this series.
Updated comment
So,
$$x_n=\sqrt{2n}\sqrt{ 1+\frac{y_n-2n}{2n}}= \sqrt{2n}\left[1+\frac{\ln(n)}{8n}+\frac{C}{4n}+\frac{\ln(n)}{32n^2}-\frac{1}{8}\left( \frac{\ln n}{4n}+\frac{C}{2n} \right)^2 +o(\frac{\ln(n)}{n^2}) \right]$$
