# 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.

-

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}}$.

-
Thanks. Excellent answer. Is there a way to get a closed recursive formula that defines A(n + 1) in terms of A(n) ? –  BrainOverfl0w May 2 '12 at 10:26
The $A(n)$ is the same as the one in the solution by Brian M. Scott, since the start is the same. The solutions are quite similar. The implicit point of view in the one I wrote is a bit more abstract, so it is slightly more suited for generalization. –  André Nicolas May 2 '12 at 13:30
@FredericJacobs: oeis.org/A053312 lists these numbers and gives a(n)=a(n-1)+10^(n-1)*(2-[a(n-1)/2^(n-1) mod 2]) as a closed form. You can think about whether it satisfies your need. –  Ross Millikan May 2 '12 at 16:58

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$.

-

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.$

-