Let the sequence ai be defined in the following way: a1=m∈Z+ and inductively ai+1=ai+⌊ai⌋. Prove that the sequence ai contains infinitely many perfect squares.
Solution
Let us analyze the sequence ai defined by a1=m and ai+1=ai+⌊ai⌋.
Suppose at some step ak is a perfect square, say ak=n2 for some integer n≥1. Then: ak+1=ak+⌊ak⌋=n2+⌊n⌋=n2+n=n(n+1)
Now, consider the next terms: ak+2=ak+1+⌊ak+1⌋ But ak+1=n(n+1), and n(n+1) is between n and n+1. Specifically, n<n(n+1)<n+1 for n≥1, so ⌊n(n+1)⌋=n. Therefore: ak+2=n(n+1)+n=n2+2n=(n+1)2−1
Now, ak+3=ak+2+⌊ak+2⌋ But ak+2=(n+1)2−1, so ak+2=(n+1)2−1. Since (n+1)2−1<(n+1)2, ak+2<n+1, and ak+2>n (since (n+1)2−1>n2 for n≥1), so ⌊ak+2⌋=n. Thus: ak+3=(n+1)2−1+n=n2+2n+n−1=n2+3n−1
But let's look for the next perfect square. Let us try to see if the sequence can reach (n+1)2. From above, ak+2=(n+1)2−1, ak+3=n2+3n−1.
Let us try to generalize. For large ai, ⌊ai⌋ increases slowly compared to ai, so the sequence grows slowly.
But more importantly, we can show that for any starting m, the sequence will eventually reach a perfect square, and then the above process repeats.
Let us prove that for any ai, there exists j>i such that aj is a perfect square.
Let ai be arbitrary. Let n=⌊ai⌋. Then n2≤ai<(n+1)2.
If ai=n2, we are done. If not, ai=n2+r for 1≤r<2n+1.
At each step, ai+1=ai+⌊ai⌋. Since ai≥n2, ai≥n, so ⌊ai⌋≥n.
Let us consider the sequence of ai modulo n:
Let us try to reach (n+1)2=n2+2n+1.
From ai=n2+r, after s steps, ai+s=n2+r+sn (since ⌊ai+t⌋=n for ai+t<(n+1)2).
We want ai+s=(n+1)2=n2+2n+1. So: n2+r+sn=n2+2n+1 r+sn=2n+1 sn=2n+1−r s=n2n+1−r
Since 1≤r<2n+1, 2n+1−r is positive and less than 2n. So s is an integer if and only if n divides 2n+1−r.
But even if s is not integer, after t steps, ai+t will reach or exceed (n+1)2, at which point ⌊ai+t⌋=n+1.
Therefore, after a bounded number of steps, the sequence will cross from n2 to (n+1)2.
Now, consider the difference ai+t−(n+1)2. For some t, ai+t will be exactly (n+1)2 if ai is congruent to n2 modulo n.
But even if not, after passing (n+1)2, the process repeats with n replaced by n+1.
Therefore, for any starting m, the sequence will eventually hit a perfect square, and then the process repeats. Thus, the sequence contains infinitely many perfect squares.
Therefore, the sequence ai 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.