# Solving a recurrence where $a_{n} =a_{n-1} +\lfloor {\sqrt {a_{n-1}}}\rfloor$

Given

$a_0 = 1$

$a_n = a_{n-1} + \lfloor{\sqrt{a_{n-1}}}\rfloor$ ; for $n > 0$

I need to find the solution of this recursion. The only thing I have noticed is that when $a_n$ is equal to or just greater than a perfect square say $x^2$ the difference between consecutive terms becomes $x$. I cannot find some expression for something like "how long the difference stays same", etc. I have thought about it for about an hour or so now, but I cannot express this in a closed form. Please give some hints or the full solution someone?

-
You're iterating $f(x)=x+\sqrt{x}$. You don't get integers for long, starting at 1: 1,2,$2+\sqrt{2}$,$2+\sqrt{2}+\sqrt{2+\sqrt{2}}$, and so on. – coffeemath Oct 24 '12 at 17:09
Sorry I edited it, I forgot to type in the floor. – Andariel Oct 24 '12 at 17:11

If you look at $\lfloor \sqrt {a_n} \rfloor$ there are two in a row of the same almost all the time. This is not surprising, because if $a_n$ is a little larger than $m^2$, and it takes two additions of $m$ to get greater than $(m+1)^2=m^2+2m+1$. The curious pattern is that it takes three when $m$ is a power of $2$. This is because you hit $m^2=2^{2p}$ exactly and two additions of $m$ just get you to $m^2+2m \lt (m+1)^2$. I haven't proven this yet, but it will allow a closed form for $a_n$ in terms of the sum of two triangular numbers plus $2^{p}-1$ for the extra powers of $2$.
A recursion that almost shows that if we ever have $a_n=2^{2p}$ the pattern is as claimed is as follows: Let $a_n=2^{2p}$. We will add three copies of $2^p$, then two copies of each integer from $2^p+1$ through $2^{(p+1)}-1$. Having done so, we will have $$a_{n+2^{(p+1)}+1}=2^{2p}+3\cdot 2^p+2\sum_{i=2^p+1}^{2^{P+1}-1} i \\=2^{2p}+3 \cdot 2^p+2\frac{(2^{p+1}-1)2^{p+1}}2-2\frac{2^p(2^p+1)}2 \\ =2^{2p+2}$$ I haven't proved we don't hit an exact square before that.
Since $a_1=1$, we can say that $$a_{2^{m+1}+m-1}=2^{2m}$$ The places you hit $2^{2p}$ are at $n=1,4,9,18,35,68 \ldots = 2^{p+1}+p-1$, which is OEIS A083706.
@Andariel: see the latest. I have shown we get 3 every time you hit a square and that hitting an even power of two you will hit the next. You don't hit any other squares, but I haven't shown that. One could get an explicit formula for all the $a_n$ now using the triangluar numbers to sum the two chains, but it takes some thinking about which bracket of powers of 2 you are in and whether there are an even or odd number of terms. – Ross Millikan Oct 24 '12 at 18:24