a1, a2, a3, ... are positive integers such that an > an-1 + 1. Put bn = a1 + a2 + ... + an. Show that there is always a square in the range bn, bn+1, bn+2, ... , bn+1-1.
Solution
If the result fails then for some m we have bn > m2 and bn+1 ≤ (m+1)2. So bn+11/2 - bn1/2 < 1. Thus it is sufficient to prove that bn+11/2 - bn1/2 ≥ 1. Squaring, that is equivalent to an+1 ≥ 2bn1/2 + 1 or bn1/2 ≤ (an+1 - 1)/2.
We have an-1 <= an - 2. So bn ≤ an + (an - 2) + (an - 4) - ... - (an - 2(n-1)). Adding extra terms to the rhs if necessary we get bn = 1 + 3 + 5 + ... + an for an odd, or 2 + 4 + 6 + ... + an for an even. In the odd case there are (an + 1)/2 terms of average size (an + 1)/2 (group them in pairs working from the outside in), so the sum is (an + 1)2/4. In the even case there are an/2 terms of average size (an + 2)/2, so the sum is an(an + 2)/4. So in either case we have bn ≤ (an + 1)2/4 and hence bn1/2 ≤ (an + 1)/2 ≤ (an+1 - 1)/2.
© John Scholes
jscholes@kalva.demon.co.uk
23 Aug 2002