Q:

Differences Equations and Theory of Numbers

The positive integers $a_0, a_1, a_2, ..., a_{3030}$ satisfy
$$
2a_{n+2} = a_{n+1}+4a_n
$$
for all $n = 0, 1, 2, ..., 3028$.
Prove that at least one of the elements $a_0, a_1, a_2, ..., a_{3030}$ is divisible by $2^{2020}$.
My kid gave me this problem and we can´t do it.  Someone could me help?  I was thinking about principle of the Pigeon Houses, but without success. 

A:

We prove by induction, assume that the statement is true for any $k\leq N$ sequence $a_0,...,a_{3k}$ satisfy
$$2a_{n+2}=a_{n+1}+4a_n$$
We will prove for case $k=N+1$.
For all $n=0,...,3N$ we have
$$a_{n+1}=2a_{n+2}-4a_n=2(2a_{n+3}-4a_{n+1})-4a_n=4(a_{n+3}-2a_{n+1}-a_n)$$
So $4 \mid a_n$ for all $n=1,...,3N+1$. The sequence $\dfrac{a_1}{4},...,\dfrac{a_{3N+1}}{4}$ satisfy the recursive condition so by assumption, there exists an element which is divisible by $4^N$. Thus, there must be an element $a_n$ which is divisible by $4^{N+1}$. 
I miss the part that clearly the statement is true for $N=1$ since $4 \mid a_1$ from same computation as above.