Prove the following sequence always results in a perfect square.

Question

There's a problem statement:

For each $m \in \mathbb{N}$, we construct a sequence $m_0$, $m_1$, $m_2,\dots$ denoted $S_m$, recursively via $m_0=m$ and

$$m_{i+1} = m_i + \left\lfloor \sqrt{m_i} \right\rfloor$$

for all $i \ge 0$. Here, $\lfloor x \rfloor$ is the floor of $x$, the greatest integer less than or equal to $x$. Hence, we have $\left\lfloor \sqrt{10} \right\rfloor=3$ and $\left\lfloor \sqrt{29} \right\rfloor=5$.

Show that for each positive integer $m$, the sequence $S_m$ contains the square of some integer.

I'm pretty certain that this can be proved with induction. I am just not quite sure what to induct on. Examining examples shows that $S_m$ always results in a perfect square eventually, though I'm not sure how to prove it.

Answer 1

Suppose our $m$ is less than some square, say, $k^2$. Then let's go up until we get over $k^2$. (If we hit it, we just stop right there.) Let's denote the first term above $k^2$ as $k^2+l$. Since the last step was less than $k$, it follows that $l<k$. It can be said that we missed this square by $l$.

Fine. Let's make two more steps. The first would get us to $k^2+k+l$, which is still less than the next square, so the $\lfloor \sqrt{m_i} \rfloor$ is still $k$. The second would get us to $k^2+2k+l = (k+1)^2+l-1$.

See that? We missed the next square by $l-1$. Well, let's do two more steps and miss the next square after that by $l-2$, and so on, until we hit some square spot on. That would be it.

Q.e.d.

Answer 2

This is not a full answer, but too long for a comment.

Looking at the number of steps necessary to reach a square, a clear pattern emerges, perhaps it can be proven that it continues forever. The last column shows the number of necessary steps and the pattern is very easy to recognize.

? for(k=1,100,m=k;t=0;while(issquare(m)==0,t=t+1;m=m+floor(sqrt(m)));print(k,"
",m,"  ",t))
1  1  0
2  4  2
3  4  1
4  4  0
5  9  2
6  16  4
7  9  1
8  16  3
9  9  0
10  16  2
11  25  4
12  36  6
13  16  1
14  25  3
15  36  5
16  16  0
17  25  2
18  36  4
19  49  6
20  64  8
21  25  1
22  36  3
23  49  5
24  64  7
25  25  0
26  36  2
27  49  4
28  64  6
29  81  8
30  100  10
31  36  1
32  49  3
33  64  5
34  81  7
35  100  9
36  36  0
37  49  2
38  64  4
39  81  6
40  100  8
41  121  10
42  144  12
43  49  1
44  64  3
45  81  5
46  100  7
47  121  9
48  144  11
49  49  0
50  64  2