INMO 2010 Problem 6

Define a sequence $\left\langle a_{n}\right\rangle_{n \geq 0}$ by $a_{0}=0, a_{1}=1$ and

$$a_{n}=2 a_{n-1}+a_{n-2}$$

for $n \geq 2$.

(a) For every $m>0$ and $0 \leq j \leq m$, prove that $2 a_{m}$ divides $a_{m+j}+(-1)^{j} a_{m-j}$.

(b) Suppose $2^{k}$ divides $n$ for some natural numbers $n$ and $k$. Prove that $2^{k}$ divides $a_{n}$.