The sequence a0, a1, a2, ... is defined by a0 = 0, a1 = 1, an+2 = 2an+1 + an. Show that 2k divides an iff 2k divides n.
Solution
Since an+2 = an mod 2, and a1 is odd, it follows that aodd is always odd. Define bn by the same recurrence relation with b0 = b1 = 2. Then obviously all bn are even, so bn+2 = bn mod 4 and hence bn = 2 mod 4 for all n.
Solving, we find an = (1 + √2)n/√8 - (1 - √2)n/√8, and bn = (1 + √2)n + (1 - √2)n. Hence anbn = a2n. 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