2
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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\}.$$ $\endgroup$ – heropup Oct 3 '17 at 6:29
  • $\begingroup$ @heropup Oops, I meant to say "powers of two appear three times". $\endgroup$ – orlp Oct 3 '17 at 6:46
  • $\begingroup$ and how do you prove this? $\endgroup$ – miracle173 Oct 3 '17 at 7:01
  • 1
    $\begingroup$ @miracle173 Then it wouldn't really be a hint anymore. $\endgroup$ – orlp Oct 3 '17 at 7:23
  • $\begingroup$ 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? $\endgroup$ – miracle173 Oct 3 '17 at 17:06
1
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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