# $\lim_{n \to \infty} (a_n - \sqrt{2n})$ if $a_1 = 1$ and $a_{n+1} = a_n +\frac{1}{a_n}$.

Put $$a_1 = 1$$ and $$a_{n+1} = a_n +\frac{1}{a_n}$$.

1) Main question: what can we say about the speed of convergence of $$\frac{a_n}{\sqrt{n}}$$ to its limit?

2) Additional question: is there a simple way to find the limit of $$\frac{a_n}{\sqrt{n}}$$?

More formally: $$\lim_{n \to \infty }\frac{a_n}{\sqrt{n}} = \sqrt{2}$$ (if there's no mistake below), what can we say about $$\frac{a_n}{\sqrt{n}} - \sqrt{2}$$, e.g. does $$\lim_{n \to \infty} (a_n - \sqrt{2n})$$ exist and can we find it in an explicit form? From direct computation in Python it follows (see above) that $$\text{Hypothesis:} \quad \lim_{n \to \infty} (a_n - \sqrt{2n}) = 0$$ is true.

What is obvious? It's easy to see that $$a_n$$ is strictly increasing and tends to $$\infty$$ (Indeed, otherwise $$a_n$$ is bounded and hence $$a_n \to a < \infty$$. Thus $$a = \lim a_{n+1} = \lim (a_n +\frac{1}{a_n}) = a +\frac{1}{a} \Longrightarrow a = a+\frac{1}{a}$$).

What else do we know? If I'm not mistaken $$\big[\sqrt{2n+\frac94} - \frac12\big] \le a_n \le \sqrt{2n}(1+o(1))$$ for all $$n > 2$$ (the proof is above) and hence $$\lim_{n \to \infty} \frac{a_n}{\sqrt{n}} = \sqrt{2}$$. Some numerical experiments are presented in the end of the question.

What are the difficulties? The upper bound for $$a_n$$ was obtained using the asymptotics of the sums $$\sum_{n=1}^{\infty} \frac{1}{[f(n)]}$$ where $$f(n) = \sqrt{2n+\frac94} - \frac12$$ and $$[x]$$ is an integer part of $$[x]$$. There are good estimates (using intergal approximation) of $$\sum_{n=1}^{\infty} \frac{1}{f(n)}$$ for good functions $$f$$, but it looks like there are no good estimates of $$\sum_{n=1}^{\infty} \frac{1}{[f(n)]}$$.

Proofs:

Lemma1. $$a_n \ge \sqrt{2n+\frac94} - \frac12$$ if $$n = \frac{k(k+1)}2-1 \ge 2$$.

Proof. Lets prove that $$a_{\frac{k(k+1)}2 - 1} \ge k$$ for $$k \ge 2$$. Put $$m_k = \frac{k(k+1)}2-1$$. We will use induction and suppose the opposite. We have: $$a_{m_k} \ge k$$ and $$a_{m_{k+1}} < k+1$$. Hence $$k \le a_{m_k} < a_{m_k + 1 } < a_{m_k + 2 } < \ldots < a_{m_{k+1}} < k+1,$$ $$a_{m_k+i+1} - a_{m_k+i} = \frac{1}{a_{m_k+i}} > \frac{1}{k+1}$$ Summing l.h.s. or the last inequality we get $$a_{m_{k+1}} - a_{m_{k}} > \frac{1}{k+1} + \frac{1}{k+1} + \ldots + \frac{1}{k+1} = \frac{m_{k+1}-m_k}{k+1}.$$ But $$a_{m_{k+1}} - a_{m_{k}} < (k+1)- k = 1$$. Thus $$1 > \frac{m_{k+1}-m_k}{k+1} \Longrightarrow m_{k+1}-m_k < k+1 \Longrightarrow \frac{(k+1)(k+2)}2 - \frac{k(k+1)}2 < k+1 \Longrightarrow$$ $$\Longrightarrow \frac{(k+2)}2 - \frac{k}2 < 1 \Longrightarrow 1 < 1.$$ We got a contradiction. Thus $$a_{m_{k+1}} \ge k+1$$. Lemma is proved.

Lemma2: $$a_n \ge \big[\sqrt{2n+\frac94} - \frac12\big]$$ for all $$n \ge 2$$.

Proof. Put $$u_n = \big[\sqrt{2n+\frac94} - \frac12\big]$$. We have $$u_n \le \sqrt{2n+\frac94} - \frac12 \Longrightarrow (u_n + \frac12)^2 \le 2n+\frac94 \Longrightarrow n \ge \frac{u_n(u_n+1)}{2}-1$$ Thus $$a_n \ge a_{\frac{u_n(u_n+1)}{2}-1} \ge u_n$$ by lemma 1.

Lemma3: $$\frac{a_n}{\sqrt{n}} \to \sqrt{2}$$ as $$n\to \infty$$.

Proof. According to lemma 2 it's sufficient to show that $$\overline{\lim}_{n \to \infty} \frac{a_n}{\sqrt{n}} \le \sqrt{2}$$.

Put $$u_n = \big[\sqrt{2n+\frac94} - \frac12\big]$$. We have $$a_{j+1} - a_j = \frac1{a_j} \le \frac{1}{u_j}$$ It follows that $$a_n = \sum_{j=3}^{n-1} (a_{j+1}-a_j) + a_2 \le 2 + \sum_{j=3}^{n-1} \frac{1}{u_j}$$ As $$u_j \sim \frac{1}{\sqrt{2j}}$$ hence $$\sum_{j=3}^{n-1} \frac{1}{u_j} \sim \sum_{j=1}^{n} \frac{1}{\sqrt{2j}} \sim \int_{1}^n \frac{dx}{\sqrt{2x}} \sim \sqrt{2n}.$$ Thus $$\overline{\lim}_{n \to \infty} \frac{a_n}{\sqrt{n}} \le \sqrt{2}$$.

Numerical experiments.

Let's compute $$b_n = a_n - \sqrt{2n}$$ for first values of $$n$$ in Python. We get $$b_{1000}=0.035513542064180115, b_{2000}=0.0278533072346292, b_{3000}=0.02405133309876817, b_{4000}=0.021633453406735725, b_{5000}=0.019907583619357183, b_{6000}=0.018589261056305872, b_{7000}=0.017536096833907777, b_{8000}=0.01666749243514687, b_{9000}=0.015933785448964954, b_{10000}=0.015302406276020974$$

Code:

tmp = 1

for i in range(1,11000):

if i % 1000 == 0:

print('i = ', i, 'a_i/sqrt_i - (2*i)^(0.5) ',  tmp - (2*i)**0.5)

tmp = tmp + 1/tmp


It looks like $$b_{n} > b_{n+1} > 0$$ and $$b_n \to 0$$ as $$n \to \infty$$.

Addition (an idea that might be helpful): there's the next idea which looks like it may be useful but I don't know how to apply it. An equation $$a_{n+1}-a_{n} = \frac{1}{a_n}$$ looks like an ODE $$y' = \frac{1}{y(t)}$$, Solving ODE we get $$2y'y = 2 + c \Longrightarrow y^2 = 2t + c\Longrightarrow y = \sqrt{2t + c}$$. Then maybe we may get properties of $$a_n$$ from the solution $$y(t) = \sqrt{2t + c}$$ if we estimate the precision of approximation of ODE by our linear recurrence relation. I am not an expert in the field of such approximations. If you think that idea with $$y(t)$$ is useful please give a hint how to bring this idea to mind.

Clearly $$\{a_n\}$$ is increasing. Suppose $$\{a_n\}$$ is bounded. Then $$\lim_{n\to\infty} a_n=a$$ exists. So one has $$a=a+\frac1a$$ which is impossible. So $$\{a_n\}$$ is unbounded and hence $$a_n\to\infty$$ as $$n\to\infty$$. By Stolz' Theorem, one has $$\begin{eqnarray} \lim_{n\to\infty} \frac{a_n^2}{n}&=&\lim_{n\to\infty} \frac{a_{n+1}^2-a_n^2}{(n+1)-n}\\ &=&\lim_{n\to\infty} (a_{n+1}-a_n)(a_{n+1}+a_n)\\ &=&\lim_{n\to\infty} \frac{2a_n+\frac1{a_n}}{a_n}\\ &=&2+\lim_{n\to\infty} \frac{1}{a_n^2}=2. \end{eqnarray}$$

• $\displaystyle +1$. Nice job. Jan 24, 2023 at 17:00
• @FelixMarin Thank you! Jan 24, 2023 at 20:06
• Thanks! I have never seen Stolz' Theorem before. Interesting. Never too old to learn :-) Jan 24, 2023 at 21:20
• @HandeBruijn, you are welcome. Jan 24, 2023 at 21:45
• @xpaul Thank you! Jan 25, 2023 at 8:16

The analysis concerning the ratio $$a_n/\sqrt{2n}$$ can be shortened. We have $$a_{n+1}^2-a_n^2=(a_{n+1}-a_n)(a_{n+1}+a_n)={a_{n+1}\over a_n}+1\ge 2$$ Hence $$a_n^2\ge 2n-1.$$ Furthermore $$a_{n+1}-a_n={1\over a_n}\le {1\over \sqrt{2n-1}}$$ Thus $$a_{n+1}\le 1+\sum_{k=1}^{n}{1\over \sqrt{2k-1 }}=2+\sum_{k=2}^n{1\over \sqrt{2k-1}}\\ \le 2+\sum_{k=2}^{n}[\sqrt{2k-1}-\sqrt{2k-3}]=1+\sqrt{2n-1}$$

Remark By considering $$a_n^2$$ gives $$a_{n+1}^2=a_n^2+2+{1\over a_n^2}$$ Similar analysis gives better estimates $$2n+2\le a_n^2\le 2n+2+{\ln n\over 2}$$ mentioned in one of the answers, although the lower estimate is wrong for small indices, e.g. $$n=1,2.$$ It should be replaced by $$a_n^2\ge 2n,$$ $$n\ge 2.$$

• @ RyszardSzwarc, Thank you! Jan 25, 2023 at 8:17

We know (see Closed form for the sequence defined by $a_0=1$ and $a_{n+1} = a_n + a_n^{-1}$) that $$2n+2\le a_n^2\le 2n+2+\frac{\ln n}{2}.$$ Hence, $$\sqrt{2n+2}-\sqrt{2n}\le b_n\le \sqrt{2n+2+\frac{\ln n}{2}}-\sqrt{2n}.$$ Using equality $$\sqrt{a}-\sqrt{b}=\frac{a-b}{\sqrt{a}+\sqrt{b}}$$ and sandwich theorem we get that $$b_n\to 0$$. Moreover, $$b_n>0$$.

• Thank you! I didn't expect that it was already almost solved. Jan 23, 2023 at 18:19

It's rather easy to prove that $$\bbox[navy,8px]{\color{white}{a_n=\sqrt{2n} + \frac{\ln n}{(4\sqrt2)\sqrt n} + o\big(\frac{\ln n}{\sqrt n}\big)}}$$, as $$n\to\infty$$ (assuming the results already proven in the question). Let's put $$u_n=a_n^2-2n$$ for $$n\geqslant0$$.

Then $$u_{n+1}=a_{n+1}^2-2(n+1) =a_n^2+2+a_n^{-2}-2n-2 =u_n + a_n^{-2}$$.

Then $$u_n=u_1+\sum^{n-1}_{k=1}(u_{k+1}-u_k) =u_1+\sum^{n-1}_{k=1} a_k^{-2}$$.

Now, since $$a_k^{-2}\sim \frac1{2k}$$ as $$k\to\infty$$, we have $$\sum^{n-1}_{k=1} a_k^{-2} \sim \sum^{n-1}_{k=1} \frac{1}{2k} \sim \frac12\ln n$$ (as $$n\to\infty$$).

We thus have $$u_n\sim\frac12\ln n$$, which lastly provides: $$\begin{eqnarray*} a_n&=&\sqrt{u_n+2n}=\sqrt{2n}\sqrt{1+\frac{u_n}{2n}}\\ &=&\sqrt{2n}\sqrt{1+\frac{\ln n}{4n}+o\Big(\frac{\ln n}{n}\Big)}\\ &=&\sqrt{2n}\bigg(1 + \frac{\ln n}{8n} + o\Big(\frac{\ln n}{n}\Big)\bigg)\\ &=&\sqrt{2n}+\frac{\ln n}{(4\sqrt2)\sqrt n} + o\bigg(\frac{\ln n}{\sqrt n}\bigg)\cdot \end{eqnarray*}$$

• It's interesting, thank you! Jan 26, 2023 at 16:54
• You're welcome. Jan 26, 2023 at 16:58