Maths Olympiad Prep

Library / /12 of 27

Algebra Difficulty 8.0 Shortlist Prove it Saudi Arabia

Let the sequence aia_i be defined in the following way: a1=mZ+a_1 = m \in \mathbb{Z}_+ and inductively ai+1=ai+aia_{i+1} = a_i + \lfloor \sqrt{a_i} \rfloor. Prove that the sequence aia_i contains infinitely many perfect squares.

Solution

Let us analyze the sequence aia_i defined by a1=ma_1 = m and ai+1=ai+aia_{i+1} = a_i + \lfloor \sqrt{a_i} \rfloor.

Suppose at some step aka_k is a perfect square, say ak=n2a_k = n^2 for some integer n1n \geq 1. Then:
ak+1=ak+ak=n2+n=n2+n=n(n+1) a_{k+1} = a_k + \lfloor \sqrt{a_k} \rfloor = n^2 + \lfloor n \rfloor = n^2 + n = n(n+1)

Now, consider the next terms:
ak+2=ak+1+ak+1 a_{k+2} = a_{k+1} + \lfloor \sqrt{a_{k+1}} \rfloor
But ak+1=n(n+1)a_{k+1} = n(n+1), and n(n+1)\sqrt{n(n+1)} is between nn and n+1n+1.
Specifically, n<n(n+1)<n+1n < \sqrt{n(n+1)} < n+1 for n1n \geq 1, so n(n+1)=n\lfloor \sqrt{n(n+1)} \rfloor = n.
Therefore:
ak+2=n(n+1)+n=n2+2n=(n+1)21 a_{k+2} = n(n+1) + n = n^2 + 2n = (n+1)^2 - 1

Now, ak+3=ak+2+ak+2a_{k+3} = a_{k+2} + \lfloor \sqrt{a_{k+2}} \rfloor
But ak+2=(n+1)21a_{k+2} = (n+1)^2 - 1, so ak+2=(n+1)21\sqrt{a_{k+2}} = \sqrt{(n+1)^2 - 1}.
Since (n+1)21<(n+1)2(n+1)^2 - 1 < (n+1)^2, ak+2<n+1\sqrt{a_{k+2}} < n+1, and ak+2>n\sqrt{a_{k+2}} > n (since (n+1)21>n2(n+1)^2 - 1 > n^2 for n1n \geq 1), so ak+2=n\lfloor \sqrt{a_{k+2}} \rfloor = n.
Thus:
ak+3=(n+1)21+n=n2+2n+n1=n2+3n1 a_{k+3} = (n+1)^2 - 1 + n = n^2 + 2n + n - 1 = n^2 + 3n - 1

But let's look for the next perfect square. Let us try to see if the sequence can reach (n+1)2(n+1)^2.
From above, ak+2=(n+1)21a_{k+2} = (n+1)^2 - 1, ak+3=n2+3n1a_{k+3} = n^2 + 3n - 1.

Let us try to generalize. For large aia_i, ai\lfloor \sqrt{a_i} \rfloor increases slowly compared to aia_i, so the sequence grows slowly.

But more importantly, we can show that for any starting mm, the sequence will eventually reach a perfect square, and then the above process repeats.

Let us prove that for any aia_i, there exists j>ij > i such that aja_j is a perfect square.

Let aia_i be arbitrary. Let n=ain = \lfloor \sqrt{a_i} \rfloor. Then n2ai<(n+1)2n^2 \leq a_i < (n+1)^2.

If ai=n2a_i = n^2, we are done. If not, ai=n2+ra_i = n^2 + r for 1r<2n+11 \leq r < 2n + 1.

At each step, ai+1=ai+aia_{i+1} = a_i + \lfloor \sqrt{a_i} \rfloor. Since ain2a_i \geq n^2, ain\sqrt{a_i} \geq n, so ain\lfloor \sqrt{a_i} \rfloor \geq n.

Let us consider the sequence of aia_i modulo nn:

Let us try to reach (n+1)2=n2+2n+1(n+1)^2 = n^2 + 2n + 1.

From ai=n2+ra_i = n^2 + r, after ss steps, ai+s=n2+r+sna_{i+s} = n^2 + r + s n (since ai+t=n\lfloor \sqrt{a_{i+t}} \rfloor = n for ai+t<(n+1)2a_{i+t} < (n+1)^2).

We want ai+s=(n+1)2=n2+2n+1a_{i+s} = (n+1)^2 = n^2 + 2n + 1.
So:
n2+r+sn=n2+2n+1 n^2 + r + s n = n^2 + 2n + 1
r+sn=2n+1 r + s n = 2n + 1
sn=2n+1r s n = 2n + 1 - r
s=2n+1rn s = \frac{2n + 1 - r}{n}

Since 1r<2n+11 \leq r < 2n + 1, 2n+1r2n + 1 - r is positive and less than 2n2n.
So ss is an integer if and only if nn divides 2n+1r2n + 1 - r.

But even if ss is not integer, after tt steps, ai+ta_{i+t} will reach or exceed (n+1)2(n+1)^2, at which point ai+t=n+1\lfloor \sqrt{a_{i+t}} \rfloor = n+1.

Therefore, after a bounded number of steps, the sequence will cross from n2n^2 to (n+1)2(n+1)^2.

Now, consider the difference ai+t(n+1)2a_{i+t} - (n+1)^2. For some tt, ai+ta_{i+t} will be exactly (n+1)2(n+1)^2 if aia_i is congruent to n2n^2 modulo nn.

But even if not, after passing (n+1)2(n+1)^2, the process repeats with nn replaced by n+1n+1.

Therefore, for any starting mm, the sequence will eventually hit a perfect square, and then the process repeats. Thus, the sequence contains infinitely many perfect squares.

Therefore, the sequence aia_i contains infinitely many perfect squares.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.