Q1 Matemática  (IMO Shortlist 1988)

Uma sequência inteira é definida por $$a_n=2a_{n-1}+a_{n-2},(n>1),a_0=0,a_1=1.$$ Prove que $2^k$ divide $a_n$ se e somente se $2^k$ divide $n$.