Induction Proof and divisibility by $2^n$

Define the $n$-digit number as follows. Let $f(1)=2$. Suppose that we have defined $f(n)$, and $2^n$ divides $f(n)$. Then define $f(n+1)$ as follows.

If $2^{n+1}$ divides $f(n)$, then $f(n+1)$ is obtained by putting a $2$ in front of the decimal expansion of $f(n)$. Or, to put it another way, $f(n+1)=2\cdot 10^n+f(n)$. If $2^{n+1}$ does not divide $f(n)$, then $f(n+1)$ is obtained by putting a $1$ in front of the decimal expansion of $f(n)$, that is, $f(n+1)=10^n+f(n)$. We show that $2^{n+1}$ divides $f(n+1)$.

Suppose first that $2^{n+1}$ divides $f(n)$. Then $f(n+1)=2\cdot 10^n+f(n)$. Note that $2\cdot 10^n$ is divisible by $2^{n+1}$, which shows that $f(n+1)$ is divisible by $2^{n+1}$.

Suppose next that $2^{n+1}$ does not divide $f(n)$. Then $f(n)\equiv 2^n\pmod{2^{n+1}}$ (the remainder when we divide $10^n$ by $2^{n+1}$ is $2^n$). But we have $10^n \equiv 2^n \pmod{2^{n+1}}$. It follows that $f(n+1)=10^n+f(n)\equiv 2^n+2^n\equiv 2^{n+1}\equiv 0\pmod{2^{n+1}}$.

Look at the first few $A(n)$:

$$\begin{array}{c|r} n&A(n)\quad\\ \hline 1&2\\ 2&12\\ 3&112\\ 4&2112\\ 5&22112\\ 6&122112\\ 7&2122112\\ 8&12122112\\ 9&212122112 \end{array}$$

Notice that each $A(n)$ extends the previous one by adding either a $1$ or a $2$ on the lefthand end. This means that in each case so far we have $A(n+1)=a_n+10^n$ or $A(n+1)=a_n+2\cdot10^n$. This suggests trying to prove that if $A(n)=k2^n$ for some integer $k$, then one of the numbers $a_n+10^n$ and $a_n+2\cdot10^n$ is a multiple of $2^{n+1}$; if you can do that, you have your induction step. HINT: Consider separately the cases $k$ even and $k$ odd, and note that $10^n=2^n5^n$.