7
$\begingroup$

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 !

3 Answers 3

8

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

  • 0
    @FredericJacobs: http://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.2012-05-02
2

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

0

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