Question 65
Define a sequence $\langle a_{n}\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\gt 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}$.
$$
a_{n}=2 a_{n-1}+a_{n-2}
$$
for $n \geq 2$.
a. For every $m\gt 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}$.