Sequence containing perfect square?

If m is itself a square, then this is obvious. Henceforth assume m is not a square.

I will prove by induction on k that, for every n, if the sequence contains some number n^2 + k and n^2 + k < (n + 1)^2, then the sequence contains a square. (Since every nonsquare m lies between two squares, it can be written in this way, so this will give you the result you want.)

Base case: k = 1. Suppose the sequence contains n^2 + 1 for some n. Then the next square after this is n^2 + 2n + 1, so we have n^2 < n^2 + 1 < n^2 + 2n + 1, and hence [sqrt(n^2 + 1)] = n, and hence the next term of the sequence is n^2 + n + 1; and again [sqrt(n^2 + n + 1)] = n by similar reasoning, so the following term of the sequence is n^2 + 2n + 1. Hence the sequence contains (n + 1)^2. This is true for every n since n was arbitrary.

Inductive step: Assume that we know that if j < k, then for every n, if the sequence contains n^2 + j for some n, with n^2 + j < n^2 + 2n + 1, then the sequence contains a square. I will prove that if the sequence contains n^2 + k for some n, with n^2 + k < n^2 + 2n + 1, then the sequence contains a square.

Suppose the sequence contains n^2 + k, with n^2 + k < n^2 + 2n + 1. Then the next term of the sequence is n^2 + n + k.

If n^2 + n + k is greater than (n + 1)^2, then it is greater than it by less than n, since n^2 + k < (n + 1)^2. Since n^2 + n + k > n^2 + 2n + 1, then also k > n, so n^2 + n + k is greater than (n + 1)^2 by less than k. So the sequence contains a term of the form (n + 1)^2 + j, with j < k, so by the inductive hypothesis the sequence contains a square.

If n^2 + n + k is equal to (n + 1)^2, then the sequence obviously contains a square.

If n^2 + n + k is less than (n + 1)^2, then the next term in the sequence is n^2 + 2n + k, which is equal to (n + 1)^2 + (k - 1), which is either a square itself, or else we may write the term as (n + 1)^2 + j with j < k, so the sequence contains a square by the inductive hypothesis.

This completes the induction.

Since every nonsquare m is between two squares, then every nonsquare m can be written in the form n^2 + k, with n^2 + k < (n + 1)^2. Hence the sequence contains a square for every m.

Obvious corollary: The sequence contains infinitely many squares for every m.

We don't have to consider the case where m is a perfect square. Consider the case where m is not.

i.e. s^2 < m < (s+1)^2

where s = integer

[√m] = s

So in the sequence, you add s to m until you get or exceed (s+1)^2. Then you add (s+1) and so on.

The difference between s^2 and (s+1)^2

= 2s+1

This means that you can add s a maximum of 2 times before you move on to the next pair of squares.

It also means that if m = s^2 + 1 < (s+1)^2,

you hit the next perfect square in 2 moves.

If follows that if m = s^2 + 2 < (s+1)^2,

you hit (s+1)^2 + 1 in 2 moves, and then (s+2)^2 in another 2 moves.

Generally if m is k more than [√m]^2, then in a couple of moves the sequence value becomes k-1 more than the next perfect square. Then every two moves this value keeps decreasing by 1 until you finally hit a perfect square.

Of course if m is closer to the higher perfect square then you can hit in fewer moves, but hit nevertheless.

*EDIT*

OK I guess this was essentially the same thing mathemagician did.