Recurrence relation problem: Given $a_n = \left \lfloor \sqrt{a_1 + a_2 + \cdots + a_{n-1}} \right \rfloor$, find $a_{1000}$.

I've been struggling with this problem for some time.

Let there be a recurrent sequence ${a_n}$ such that $a_1 = 1$ and $a_n = \left \lfloor\sqrt{a_1 + a_2 + \cdots + a_{n-1}}\right \rfloor$ for all $n > 1$. Find $a_{1000}$.

I've tried to plug in different $n$ and have noticed that the square root makes it grow slowly, and with bigger $n$ the terms become more distinct (different integers), but that still hasn't gotten me close to solving for $a_{1000}$.

Update: I've solved it. I will post my solution in a bit. The hints you guys have given me have proved valuable, and I appreciate the caution with which you guys go about giving me a full solution based on my lack of steps taken.

• The sequence is registered in the OEIS as A109964 – miracle173 Oct 3 '17 at 23:08

Hint: $1$ appears four times in the series, powers of two appears three times, and all other numbers appear exactly twice.

• This is not actually correct. A quick manual computation demonstrates that the sequence begins as $$\{1,1,1,1,2,2,2,3,3,4,4,4,5,5,\ldots\}.$$ – heropup Oct 3 '17 at 6:29
• @heropup Oops, I meant to say "powers of two appear three times". – orlp Oct 3 '17 at 6:46
• and how do you prove this? – miracle173 Oct 3 '17 at 7:01
• @miracle173 Then it wouldn't really be a hint anymore. – orlp Oct 3 '17 at 7:23
• does this mean you have a proof but you don't publish it here or does this mean you generated a lot of elements of this sequence, looked at them and deduced that your statement may be true? – miracle173 Oct 3 '17 at 17:06

If we write down some of the first numbers, we get: $(1,1,1,1,2,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,8,9,9,…)$. From this it is visible that number $1$ appears four times, while all other numbers appear twice, thrice at most. We will further define that numbers that appear thrice are the powers of $2$, starting with $2^1$. All other numbers therefore appear twice.

Suppose we wrote down the beginning of the sequence until the first occurrence of the number $n \ (n>1)$, and that the sequence visibly behaves as defined.

Let $k$ be the largest integer satisfying $2^{k}$. Then the sum of all the values is:

$s_1 = (1+2+...+n) + (1+2+...+n-1) + (1+2+2^2+...+2^k) +1 = n^2 + 2^{k+1}$

since $2^{k+1} = 2 \times 2^k < 2n < 2n +1 = (n+1)^2 - n^2$. We have $s_1 < (n+1)^2$ and the following member is therefore $\lfloor\sqrt{s_1}\rfloor = n$.

Now we define the next member in this order, and the sum is now:

$s_2 = s_1 + n = n^2 + n + 2^{k+1}$,

so if $2^{k+1} < n+1$, then $s_2 < (n+1)^2$ and the next member is $n$.

However, $k$ is the largest integer satisfying $2^k < n$, so it's true that $n\le 2^{k+1}$. The previous situation therefore occurs iff $2^{k+1} = n$.

When $n$ isn't a power of two, the next member is $n+1$, because $n+1\le 2^{k+1} < 2n < 3n +4$, which follows from $(n +1)^2 \le n^2 + n + 2^{k+1} < (n+2)^2$.

Now we only need to show that if $n = 2^{k+1}$, then after three occurrences of $n$, an $n+1$ will follow.

Now the sum is:

$s_3 = s_2 + n = n^2 + 2n + 2^{k+1} = n^2 + 3n$, and we immediately get the inequality $(n+1)^2 < s_3 < (n+2)^2$.

Now we finally see that $500 = a_{1010} = a_{1009}$. Thus, $a_{1000} = \boxed{495}$.