Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
@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
    
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. –  Andariel Oct 24 '12 at 18:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.