Indian National Mathematical Olympiad

Solution:

a.
Consider $f(j)=a_{m+j}+(-1)^{j} a_{m-j}$, $0 \leq j \leq m$, where $m$ is a natural number. We observe that $f(0)=2 a_{m}$ is divisible by $2 a_{m}$. Similarly,
$$f(1)=a_{m+1}-a_{m-1}=2 a_{m}$$
is also divisible by $2 a_{m}$. Assume that $2 a_{m}$ divides $f(j)$ for all $0 \leq j<l$, where $l \leq m$. We prove that $2 a_{m}$ divides $f(l)$. Observe
$$\begin{aligned} & f(l-1)=a_{m+l-1}+(-1)^{l-1} a_{m-l+1} \\ & f(l-2)=a_{m+l-2}+(-1)^{l-2} a_{m-l+2} \end{aligned}$$
Thus we have
$$\begin{aligned} a_{m+l} & =2 a_{m+l-1}+a_{m+l-2} \\ & =2 f(l-1)-2(-1)^{l-1} a_{m-l+1}+f(l-2)-(-1)^{l-2} a_{m-l+2} \\ & =2 f(l-1)+f(l-2)+(-1)^{l-1}\left(a_{m-l+2}-2 a_{m-l+1}\right) \\ & =2 f(l-1)+f(l-2)+(-1)^{l-1} a_{m-l} \end{aligned}$$
This gives
$$f(l)=2 f(l-1)+f(l-2)$$
By induction hypothesis $2 a_{m}$ divides $f(l-1)$ and $f(l-2)$. Hence $2 a_{m}$ divides $f(l)$. We conclude that $2 a_{m}$ divides $f(j)$ for $0 \leq j \leq m$.

b.
We see that $f(m)=a_{2 m}$. Hence $2 a_{m}$ divides $a_{2 m}$ for all natural numbers $m$. Let $n=2^{k} l$ for some $l \geq 1$. Taking $m=2^{k-1} l$, we see that $2 a_{m}$ divides $a_{n}$. Using an easy induction, we conclude that $2^{k} a_{l}$ divides $a_{n}$. In particular $2^{k}$ divides $a_{n}$.