Induction Proof and divisibility by $2^n$ I'm trying to use induction to prove that for every integer $n > 0$ there exists an $n$-digit integer A(n) that is divisible by $2^n$ and that consists entirely of digits “1” and “2”.
Does anyone have a clue where to start ?
I found examples that work on small numbers and the initial step of the induction proof is not an issue. I need to prove it for $n+1$ now.
Thanks for any advise !
 A: 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}}$.
A: 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$.
A: Hint $\  $  More generally if $\rm\:a_n = e\!\:c^n\:$ has $\rm\:n\:$ digits all $\rm\in [1,c]\:$ in radix $\rm\:bc,\ (b,c)=1, \:$ then
$$\rm\  c^{n+1}\:|\: d\:\!(bc)^n+e\!\:c^n \iff c\:|\: d\:\!b^n + e\iff d\equiv -e/b^n\ (mod\ c)$$
Choosing such $\rm\:d\in [1,c],\:$ we obtain an $\rm\:a_{n+1}\:$ divisible by $\rm\:c^{n+1}$ having $\rm\:n\!+\!1\:$ digits all $\rm\in [1,c],\:$ because $\rm\:a_{n+1}\:$ is constructed from $\rm\:a_n\:$ by prepending the new leading digit $\rm\:d.$ 
