# A limit about $a_1=1,a_{n+1}=a_n+[\sqrt{a_n}]$

Let the sequence $\{a_n\}$ satisfy $$a_1=1,a_{n+1}=a_n+[\sqrt{a_n}]\quad(n\geq1),$$ where $[x]$ is the integer part of $x$. Find the limit $$\lim\limits_{n\to\infty}\frac{a_n}{n^2}$$.

Add: By the Stolz formula, we have \begin{align*} &\mathop {\lim }\limits_{n \to \infty } \frac{{{a_n}}}{{{n^2}}} = \mathop {\lim }\limits_{n \to \infty } \frac{{{a_{n + 1}} - {a_n}}}{{2n + 1}} = \mathop {\lim }\limits_{n \to \infty } \frac{{\left[ {\sqrt {{a_n}} } \right]}}{{2n + 1}} = \frac{1}{2}\mathop {\lim }\limits_{n \to \infty } \left( {\left[ {\sqrt {{a_{n + 1}}} } \right] - \left[ {\sqrt {{a_n}} } \right]} \right)\\ = &\frac{1}{2}\mathop {\lim }\limits_{n \to \infty } \left( {\left[ {\sqrt {{a_n} + \left[ {\sqrt {{a_n}} } \right]} } \right] - \left[ {\sqrt {{a_n}} } \right]} \right) = \frac{1}{2}\mathop {\lim }\limits_{x \to \infty } \left( {\left[ {\sqrt {x + \left[ x \right]} } \right] - \left[ {\sqrt x } \right]} \right).\end{align*} But it seems no use!

• @NormalHuman Ok! – Eufisky Oct 18 '15 at 6:40
• The last limit doesn't exists since as $x$ changes from $k^2-\epsilon$ to $k^2$, the first term barely changes and the second term jumps up by 1 but the original limit is $\frac 1 4$ as shown by Christian below. – A.S. Oct 18 '15 at 7:42
• See OEIS A$2984$. – Lucian Oct 18 '15 at 23:53

Let $b_n$ solve the recursion $b_{n+1}^2=b_n^2+b_n$, $b_1=1$. Then $b_n^2\ge a_n$ (I "forgot" the floor function, otherwise this is the original recursion for $\sqrt{a_n}$). So $$b_{n+1} = b_n + \frac{1}{2} + O(b_n^{-1}) .$$ Now clearly $a_n\ge 1$, so $a_n\gtrsim n$ (from the recursion), so $O(b_n^{-1})\lesssim n^{-1/2}$. It follows that $b_n =n/2 + O(n^{1/2})$, so $b_n^2/n^2\to 1/4$.
We can similarly bound the floor function from above by $\sqrt{a_n}+1$, which will produce the recursion $c_{n+1}^2=c_n^2+c_n+1$, which can be discussed in the same way. We conclude that $\lim a_n/n^2=1/4$.
• Would the downvoter please point out what the problem is? It's not my fault after all that the limit equals $1/4$. – user138530 Oct 18 '15 at 7:50