<s>[INST] 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}), ...
$)?
 [/INST] 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$.
</s>