A finite sequence of integers a0, a1, ... , an is called quadratic if |a1 - a0| = 12, |a2 - a1| = 22, ... , |an - an-1| = n2. Show that any two integers h, k can be linked by a quadratic sequence (in other words for some n we can find a quadratic sequence ai with a0 = h, an = k). Find the shortest quadratic sequence linking 0 and 1996.
Solution
We have to show that with a suitable choice of n and the signs ± we can get ±12 ± 22 ± 32 ± ... ± n2 = m for any integer m. Obviously if is sufficient to consider m non-negative.
n2 - (n+1)2 - (n+2)2 + (n+3)2 = 4, so we can do any m = 0 mod 4. For example, 8 = (12 - 22 - 32 + 42) +( 52 - 62 - 72 + 82).
Similarly
1 + (22 - 32 - 42 + 52) + ... gives m = 1 mod 4
-1 - 22 - 32 + 42 + (52 - 62 - 72 + 82) + ... gives m = 2 mod 4
-1 + 22 + (32 - 42 - 52 + 62) + ... gives m = 3 mod 4
For 1996 we have 1 + 22 + 32 - 42 - 52 + 62 + 72 + 82 + 92 + 102 + 112 + 122 + 132 - 142 + 152 + 162 + 172 + 182 + 192 = 1996, giving the sequence 0, 1, 5, 14, -2, -27, 9, 58, 122, 203, 303, 424, 568, 737, 541, 766, 1022, 1311, 1635, 1996.
Since 12 + 22 + ... + 172 = 1785 < 1996, we need at least 19 terms. We have 12 + 22 + ... + 182 = 2109 = 1996 + 113. But any sum ±12 ± 22 ± ... ± 182 = 12 + 22 + ... + 182 - 2(a sum of squares), so it must be odd, whereas 1996 is even. Hence 20 terms is the best possible.
© John Scholes
jscholes@kalva.demon.co.uk
20 Dec 2002