Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 !

share|improve this question

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer
    
Thanks. Excellent answer. Is there a way to get a closed recursive formula that defines A(n + 1) in terms of A(n) ? –  fred 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$.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.