The sequence a1, a2, a3, ... is constructed as follows. a1 = 1. an+1 = an - 2 if an - 2 is a positive integer which has not yet appeared in the sequence, and an + 3 otherwise. Show that if an is a square, then an > an-1.
Solution
We show by induction that a5n+1 = 5n+1, a5n+2 = 5n+4, a5n+3 = 5n+2, a5n+4 = 5n+5, a5n+5 = 5n+3. It is easy to check that a1 = 1, a2 = 4, a3 = 2, a4 = 5, a5 = 3, which establishes n = 1.
So now suppose the result is true for n and smaller. Then in particular a5n+5 - 2 = 5n+1 is already in the sequence. Hence a5n+6 = a5n+5 + 3 = 5(n+1)+1. Similarly a5n+6 - 2 = 5n+4 is already in the sequence, so a5n+7 = a5n+6 + 3 = 5(n+1)+4. But 5(n+1)+2 = a5n+7 - 2 is not yet in the sequence, so a5n+8 = 5(n+1)+2. 5(n+1) is already in the sequence, so a5n+9 = a5n+8 + 3 = 5(n+1)+5. 5(n+1)+3 is not yet in the sequence, so a5n+10 = a5n+9 - 2 = 5(n+1)+3. So we have established the result for n+1 and hence for all n.
Now any square must be 0, 1 or 4 mod 5, so it must be a5n+4, a5n+1 or a5n+2, which all satisfy the required condition.
© John Scholes
jscholes@kalva.demon.co.uk
20 December 2003