Solve $A_n=A_{n-1}+\lfloor \sqrt{A_{n-1}}\rfloor$

Solution 1:

I'll use $r(x) = \lfloor \sqrt{x}\rfloor$ throughout.

Warm Up Here's some stuff we'll use freely in the next section. It's motivated by the next section though.

What's the floor of the square root of $m^2+7m+5$? You can read it off this table:

$$\begin{array}{|c|c|c|} \hline m+k & m^2 + 2km + k^2 \\ \hline m+1 & m^2 + 2m + 1 \\ m+2 & m^2 + 4m + 4 \\ m+3 & m^2 + 6m + 9 \\ m+4 & m^2 + 8m + 16 \\ m+5 & m^2 + 10m + 25 \\ m+6 & m^2 + 12m + 36 \\ m+7 & m^2 + 14m + 49 \\ \hline \end{array}$$

It must be $m+3$.. but we do need $2k < m$ to use this table. It's easy to find counterexamples (e.g. $r(3^2+7\cdot 3+5)=5$).

Using this we can push your idea of starting with a generic $A_n = m^2$ much further and see the recurrence:

$$\begin{array}{|l|l|} \hline A_n & r(A_n) \\ \hline m^2 & m \\ m^2 + m & m \\ m^2 + 2m & m \\ m^2 + 3m & m + 1 \\ m^2 + 4m + 1 & m + 1 \\ m^2 + 5m + 2 & m + 2 \\ m^2 + 6m + 4 & m + 2 \\ m^2 + 8m + 6 & m + 3 \\ \end{array}$$

of course with the same caveat as before.

To try to formulate the pattern in this table (in order to prove it by induction) we get exactly the key insight you mentioned.