# 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}), ...$$)?

• Commented Nov 30, 2020 at 5:20
• Perhaps relevant: oeis.org/A073833 and cs.uwaterloo.ca/journals/JIS/VOL12/Kimberling/kimberling56.pdf Commented Dec 1, 2020 at 13:58
• According to the comments in oeis.org/A073833 , for $a=1$ $y_n = 2n + \frac12 \log(n) + \frac12 \log(c_1)$ where $c_1 \approx 0.574810274671785$ ( oeis.org/A232975 ) Commented Dec 1, 2020 at 14:07
• Thanks for all these. Commented Dec 1, 2020 at 16:17
• Of course, I meant $y_n = 2n + \frac12 \log(n) + \frac12 \log(c_1) + o(1)$ Commented Dec 1, 2020 at 16:26

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

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

• Thanks. I'll check my proof again. Commented Nov 30, 2020 at 7:29
• It's weird. I find my proof okay. The first equation is still equivalent to $y_{n+1}= y_n+\frac{1}{y_n}+2$. Other parts seem also okay. May you help me by telling me where I may have made an error? Commented Nov 30, 2020 at 7:38
• I also think that's the dominant term, then after adding up, I have: $$-u_N = \sum_{n \ge N} -\frac{\ln n}{4ny_N} +\text{something}$$, which is equivalent to $$u_N = \sum_{n \ge N} \frac{\ln n}{4ny_N} +\text{something}$$From which I conclude the approximation of $u_N$. I don't really think I dropped here. Perhaps, you were right with your previous formula? Commented Nov 30, 2020 at 7:58
• Oh, I see where I went wrong now, my bad. Commented Nov 30, 2020 at 7:59
• You can re-write the last expression as $$x_n \sim \sqrt {2n} \left( {1 + \frac{{\log n + 2C}}{{8n}} - \frac{{\log ^2 n + 4(C - 1)\log n + 4C^2 }}{{128n^2 }} + \cdots } \right),$$ suggesting that the general result might be of the form $$x_n \sim \sqrt {2n} \sum\limits_{k = 0}^\infty {\frac{{P_k (\log n)}}{{n^k }}} ,$$ where the $P_k$'s are some polynomials of degree $k$.
– Gary
Commented Nov 30, 2020 at 9:05