<s>[INST] The limit and asymptotic analysis of $a_n^2 - n$ from $a_{n+1} = \frac{a_n}{n} + \frac{n}{a_n}$ I came up with the following question which is the follow up of
How to prove that for $a_{n+1}=\frac{a_n}{n} + \frac{n}{a_n}$ , we have $\lfloor a_n^2 \rfloor = n$?

Problem: Let $a_1 = 1,\quad a_{n+1} = \frac{a_n}{n} + \frac{n}{a_n},\quad n\ge 1$.

*

*Prove that $\lim_{n\to \infty} (a_n^2 - n) = \frac{1}{2}$;

*Give the asymptotic analysis of $a_n^2 - n - \frac{1}{2}$.


Edit (2021/02/16) I also posted in https://mathoverflow.net/questions/384047/asymptotic-analysis-of-x-n1-fracx-nn2-fracn2x-n-2
For 1), I use the mathematical induction to prove the claim
$$n + \frac{1}{2} - \frac{2}{n} < a_n^2 < n + \frac{1}{2} + \frac{13}{4n} + \frac{13}{8n^2} + \frac{157}{16n^3}, \quad n \ge 22. \tag{1}$$
However, we need to verify it for $n = 22$ (a computer is required).
Are there simpler solutions?
$\color{blue}{\textbf{Edit}}$ 2021/02/15:
For 1), there is a solution in [1] (I know it from @haidangel's post The variation of a Ukrainian Olympiad problem: 10982). The authors proved that
$\frac{n^2}{n-1/2} \le a_n^2 \le \frac{(n-1/2)^2}{n-3/2}$ for all $n\ge 3$.
[1] Yuming Chen, Olaf Krafft and Martin Schaefer, “Variation of a Ukrainian Olympiad Problem: 10982”,
The American Mathematical Monthly, Vol. 111, No. 7 (Aug. - Sep., 2004), pp. 631-632
For 2), I have no idea currently. I want to find something like: for example, for the recurrence relation
$b_0 = 1, b_{n+1} = b_n + \frac{1}{b_n}, n\ge 0$,
we have $b_n \sim \sqrt{2n} + \frac{\sqrt{2}}{8\sqrt{n}}\ln n + o(\frac{\ln n}{\sqrt{n}})$. (Thank @Diger for pointing out the mistake. See the comment.)
About how to construct the claim (1): I want to find $d_n, c_n$ such that, for sufficiently large $n$,
$$n + \frac{1}{2} - d_n < a_n^2 < n + \frac{1}{2} + c_n.$$
To use the the mathematical induction, we need
$$a_{n+1}^2 = \frac{a_n^2}{n^2} + \frac{n^2}{a_n^2} + 2
< \frac{n + \frac{1}{2} + c_n}{n^2} + \frac{n^2}{n + \frac{1}{2} - d_n} + 2
< n + 1 + \frac{1}{2} + c_{n+1},$$
$$a_{n+1}^2 = \frac{a_n^2}{n^2} + \frac{n^2}{a_n^2} + 2
> \frac{n + \frac{1}{2} - d_n}{n^2} + \frac{n^2}{n + \frac{1}{2} + c_n} + 2
> n + 1 + \frac{1}{2} - d_{n+1}$$
which results in
$$c_{n+1} - \frac{c_n}{n^2} > \frac{n + \frac{1}{2}}{n^2} + \frac{n^2}{n + \frac{1}{2} - d_n} + \frac{1}{2} - n,$$
$$c_n < \frac{n^2}{n - \frac{1}{2} - d_{n+1} - \frac{n + \frac{1}{2} - d_n}{n^2}} - n - \frac{1}{2}.$$
We first choose $d_n$, then determine $c_n$.
For example, $d_n = \frac{2}{n}$ and $c_n = \frac{13}{4n} + \frac{13}{8n^2} + \frac{157}{16n^3}$.
 [/INST] Since $a_1=1>0$ it is clear that $a_n>0$ for all $n$. Squaring gives $$a_{n+1}^2 = \frac{a_n^2}{n^2} + \frac{n^2}{a_n^2} + 2$$ and defining $a_n^2=nb_n$, this recurrence becomes $$b_{n+1}=\frac{b_n}{n(n+1)} + \frac{n}{(n+1)b_n} + \frac{2}{n+1}$$
with $b_1=1$. Now suppose $$1\leq b_n \leq 1+\frac{1}{n}+ \frac{2}{n^2}$$
which is true for $b_2=2$, $b_3=4/3$ and $b_4=(13/12)^2$ and continue inductively, i.e.
$$b_{n+1}\geq \frac{1}{n(n+1)} + \frac{n}{(n+1)(1+1/n+2/n^2)} + \frac{2}{n+1} = 1 + \frac{3n+2}{n(n+1)(n^2+n+2)}\geq 1$$
and also $$b_{n+1}\leq \frac{1+1/n+2/n^2}{n(n+1)} + \frac{n}{n+1} + \frac{2}{n+1} \\ = 1 + \frac{1}{n+1} + \frac{2}{(n+1)^2} - \frac{1-2/n-3/n^2-2/n^3}{(n+1)^2} \leq 1 + \frac{1}{n+1} + \frac{2}{(n+1)^2}$$
whenever $n\geq 4$. Taking the limit on both sides it follows $$\lim_{n\rightarrow \infty} b_n = 1 \, .$$ Next we formally write $b_n$ as an asymptotic expansion $$b_n = 1 + \sum_{k=1}^\infty \frac{c_k}{n^k}$$ and insert it into $$(n+1)b_{n+1}b_n - \frac{b_n^2}{n} - 2b_n - n = 0$$ which gives after some extensive algebra
$$0 = 2c_1 - 1 \\
+ \sum_{m=1}^\infty \frac{1}{n^m} \left\{ \sum_{k=0}^m (c_{m-k} + c_{m+1-k}) \sum_{l=0}^k \binom{-l}{k-l} c_l + \sum_{l=0}^{m+1} \binom{-l}{m+1-l} c_l - \sum_{k=0}^{m-1} c_k c_{m-1-k} - 2c_m \right\} \, .$$
Setting the coefficient of each power $n^{-m}$ to zero, iteratively gives a linear equation for $c_{m+1}$ ($m=1,2,3,...$) in terms of $c_0=1$ and $c_k$ ($k=1,2,...,m$). The coefficient of $n^0$ already gives $c_1=1/2$.
The first higher coefficients read: $c_2=5/8, c_3=13/16, c_4=155/128, c_5=505/256$. The denominator seems to follow a power of $2$ pattern.
</s>