Let 1/(1 - 2x - x^{2}) = s_{0} + s_{1}x + s_{2}x^{2} + ... . Prove that for some f(n) we have s_{n}^{2} + s_{n+1}^{2} = s_{f(n)}.

**Solution**

Multiplying across, we have 1 = (1 - 2x - x^{2})(s_{0} + s_{1}x + s_{2}x^{2} + ... ) = s_{0} + (s_{1} - 2s_{0})x + (s_{2} - 2s_{1} - s_{0})x^{2} + ... + (s_{n} - 2s_{n-1} - s_{n-2})x^{n} + ... . Hence, the first few terms are: s_{0} = 1, s_{1} = 2, s_{2} = 5, s_{3} = 12, s_{4} = 29, s_{5} = 70, s_{6} = 169. Also we have the recurrence relation s_{n} = 2s_{n-1} + s_{n-2} (*).

For the early terms, we find: s_{0}^{2} + s_{1}^{2} = s_{2}, s_{1}^{2} + s_{2}^{2} = s_{4}, s_{2}^{2} + s_{3}^{2} = s_{6}. So it is natural to conjecture that s_{n}^{2} + s_{n+1}^{2} = s_{2n+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 s_{0} and s_{1} gives s_{n} = ( (1 + √2)^{n+1} - (1 - √2)^{n+1} )/(2√2). Hence s_{n}^{2} + s_{n+1}^{2} = 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) = s_{2n+2}.

*Omer Angel* sent me a much more elegant derivation. We get to (*) as before. Then we note that s_{n} 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 s_{n-1}^{2} possibilities. If not, then there are s_{n}^{2} possibilities. Hence s_{2n} = s_{n}^{2} + s_{n-1}^{2}.

© John Scholes

jscholes@kalva.demon.co.uk

14 Dec 1999