3
$\begingroup$

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?

  • 0
    Sorry I edited it, I forgot to type in the floor.2012-10-24

1 Answers 1

5

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.

  • 0
    Ah, I see, nice. Thanks for the whole procedure of solution, I feel I couldn't have done it if someone game me just hints. Thank you. +100 if I could.2012-10-24