find the smallest n such that $a_n > 2019$

Question

Source: Question 11 of this problem set. I'd like to point out that I'm not cheating on any contest by posting this problem (e.g. the OTIS). It was released in the past to help students prepare for the Putnam competition.

Let $a_1 = 1, a_{n+1} = a_n + \lfloor \sqrt{a_n}\rfloor$ for $n\ge 1$. Find, with proof, the smallest $n$ such that $a_n > 2019$?

My first instinct is to try to guess a formula for $a_n$ that can hopefully be easily proven via induction. Alternatively one may be able to prove some useful properties about the sequence using induction. We have $\lfloor \sqrt{a_n}\rfloor = k\Leftrightarrow k^2 \leq a_n \leq k^2 + 2k.$ Computing the first few terms of the sequence gives $1,2,3,4,6,8,10,13,16,20,24,28,33,38.$ But there doesn't seem to be any noticeable pattern that can lead to a general formula. However, observing the perfect squares in the sequence, we see that the only two seen so far are $4$ and $16$. It might not just be a coincidence that these are both powers of 4 (1). Then it might be useful to consider the number of times $\lfloor \sqrt{a_n}\rfloor$ occurs. The sequence $\lfloor \sqrt{a_n}\rfloor$ is as follows: $1,1,1,2,2,2,3,3,4,4,4,5,5,6$. Again, it may not be a coincidence that the values that occur $3$ times in this small sample are powers of 2 while all other values occur exactly twice (2). Assume that hypotheses (1) and (2) hold for all $n\leq k, k\ge 14$. We want to show they still hold for $k+1$. Let $4^q \leq k+1 < 4^{q+1}.$ We have for $n\ge 2$ that $a_n = 1 + \sum_{i=1}^{n-1} \lfloor \sqrt{a_n}\rfloor.$ I'm not sure how to prove the inductive step from here.

Answer 1

Variation of the proof from AoPS. (we use the fact that the only squares are the powers of $4$ as given there).

Between any two squares $k^2$ and $(k+1)^2$, there are exactly two elements. Note $44^2 = 1936$ and $45^2 = 2025$.

If we count the gap between $1^2$ and $2^2$ as $1$, we have $44$ such gaps accounting for $88$ elements.

Then we include $1,4,16,64,256,1024$ or $6$ elements. So the largest element less than $2025$ is $a_{94}$.

The first element after $32^2$ has a gap of $32$ and this gap between each successive square and the first element following that goes down by $1$ until we hit $4096$. So the first element after $44^2$ will be $32-12$ away or $= 1936 + 20 = 1956$. The next one will be at $1956 + 44 = 2000$.

So $a_{95} > 2019.$

Answer 2

Denote your original sequence ${1, 2, 3, 4, 6, 8, 10, 13, 16, 20, 24, 28, 33, 38...}$ as ${a_n}$, and your sequence of the differences of the original sequence ${1, 1, 1, 2, 2, 2, 3, 3...}$ as ${b_n}$.

Notice that $(n+1)^2-n^2=2n+1$. So whenever your sum of b_n progresses $2i+1$, the value of $b_n$ will go from $i$ to $i+1$, $i$ is a positive integer.

For example, the first three terms of ${b_n}$ are $1, 1, 1$. The sum $1+1+1=3=2*1+1$, so the value of $b_n$ increase by $1$, and for the next value, namely $b_4$, you see that $b_4=2$.

Let's proceed with the same method and see what pattern we can find. $2+2+2>2*2+1$, and exceed the value $2*2+1$ by one. Since we have an extra "one", we only need to add the number "$3$" two times to get $3*2+1$. That's why you see the number $3$ only appeared two times in the sequence ${b_n}$. Now let's continue with the number $4$. you observe that $4+4+4$ exceed $4*2+1$ by three, so we only need to add the number $5$ two times and we still have a extra $2$. We next proceed to the number $6$, and we only need to add it 2 times and still have an extra one. We then proceed to number $7$, and we add it two times and found the sum is exactly 64, the square of 8 (and when you proceed with $a_n$ you will find 64 is also in $a_n$, this is not a coincidence).

Now observe what we get. For most of the numbers we only need to add them two times, but for some special numbers we need to add them three times. From our computation, the last number we should add three times is $8$. After adding $8$ three times we will get an extra $7$, so for the next 7 numbers we only need to add them two times. The next number we need to add three time is $8+7+1=16$, and the next one is $16+15+1=32$...

So we find the special numbers we need to add three times. They are ${1, 2, 2^2, 2^3, 2^4...}$

So the later computation will be easy. Denote $c_i=1,1,1,1,2,2,2,3,3,4,4,4...$ (i.e, adding the first term "$1$" to the front of the sequence $b_i$). Since $a_n=\sum_{i=1}^{n}c_i$, we only need to determine when the partial sum of $c_n$ exceed 2019.

Lets try with $\sum_{i=1}^{N}c_i$, where $c_N=32$ and $c_{N+1}=33$. The sum equals to $(1+2+...+32)*2+(1+2+4+8+16+32)+1=1120<2019$. $2019-1120=899$, and $2*(33+34+...+44)=924>899$, so we need to find m such that $c_m=44$ and $c_{m+1}=45$.

Since there are $6$ "special numbers" (i.e., $1, 2, 4, 8, 16, 32$) from $1$ to $44$, $m=44*2+6+1=95$. $95$ is the number you desire.