Let 1/(1 - 2x - x2) = s0 + s1x + s2x2 + ... . Prove that for some f(n) we have sn2 + sn+12 = sf(n).
Solution
Multiplying across, we have 1 = (1 - 2x - x2)(s0 + s1x + s2x2 + ... ) = s0 + (s1 - 2s0)x + (s2 - 2s1 - s0)x2 + ... + (sn - 2sn-1 - sn-2)xn + ... . Hence, the first few terms are: s0 = 1, s1 = 2, s2 = 5, s3 = 12, s4 = 29, s5 = 70, s6 = 169. Also we have the recurrence relation sn = 2sn-1 + sn-2 (*).
For the early terms, we find: s02 + s12 = s2, s12 + s22 = s4, s22 + s32 = s6. So it is natural to conjecture that sn2 + sn+12 = s2n+2. It might seem that the obvious way to prove this is by induction using the recurrence relation (*), but after some fruitless fiddling around, I decided it would be easier to solve (*) and use the solution.
The associated quadratic has roots 1 ±√2, so the general solution of the recurrence relation is A(1 + √2)n + B(1 - √2)n. Using the values for s0 and s1 gives sn = ( (1 + √2)n+1 - (1 - √2)n+1 )/(2√2). Hence sn2 + sn+12 = 1/8 ( (1 + √2)2n+2 - 2 (-1)n+1 + (1 - √2)2n+2) + 1/8 ( (1 + √2)2n+4 - 2 (-1)n+2 + (1 - √2)2n+4) = 1/8 (1 + √2)2n+2(1 + 3 + 2√2) + 1/8 (1 - √2)2n+2(1 + 3 - 2√2) = (1 + √2)2n+3/(2√2) - (1 - √2)2n+3/(2√2) = s2n+2.
Omer Angel sent me a much more elegant derivation. We get to (*) as before. Then we note that sn is the number of ways of tiling a 1 x n rectangle with a supply of 1 x 2 red tiles, 1 x 1 black tiles and 1 x 1 white tiles (the early values are the same and the recurrence relation is satisfied). Now consider a 1 x 2n rectangle. Either there is a centrally placed 1 x 2 tile or not. If so, then there are sn-12 possibilities. If not, then there are sn2 possibilities. Hence s2n = sn2 + sn-12.
© John Scholes
jscholes@kalva.demon.co.uk
14 Dec 1999