The sequence a_{0}, a_{1}, a_{2}, ... is defined by a_{0} = 0, a_{1} = 1, a_{n+2} = 2a_{n+1} + a_{n}. Show that 2^{k} divides a_{n} iff 2^{k} divides n.

**Solution**

Since a_{n+2} = a_{n} mod 2, and a_{1} is odd, it follows that a_{odd} is always odd. Define b_{n} by the same recurrence relation with b_{0} = b_{1} = 2. Then obviously all b_{n} are even, so b_{n+2} = b_{n} mod 4 and hence b_{n} = 2 mod 4 for all n.

Solving, we find a_{n} = (1 + √2)^{n}/√8 - (1 - √2)^{n}/√8, and b_{n} = (1 + √2)^{n} + (1 - √2)^{n}. Hence a_{n}b_{n} = a_{2n}. The required result is now a trivial induction on k.

© John Scholes

jscholes@kalva.demon.co.uk

30 Dec 2002

Last corrected/updated 30 Dec 02