Using induction, prove for every $n \in \mathbb{N}$, there exists number of $n$ digits $M_n$ = $a_1$, $a_2$,... $a_n$, ...$2^n$ divides $M_n$

Question

Using induction, prove for every $n \in \mathbb {N}$, there exist a number of $n$ digits $M_n$ = $a_1$, $a_2$,... $a_n$ with $a_i \in \{2,3\}$ such that $2^n$ divides $M_n$.

I understand how induction works, with proving the base step and then assuming the next possible entry after that, but what exactly is the base step in this problem? And after the base step, what would my induction step look like?

So far the only induction problems I've worked are relatively straightforward such as $n! \ge 2^n$ for any $n \ge 4$, so if you can, please try to simplify it down to that level of difficulty.

Thanks, and sorry for not placing the entire formula into the title, it wouldn't fit.

Answer 1

The base step want you to give a one digit number $M_1$ having only 2s and 3s as digits, which is a multiple of $2^1 = 2$. Obviously $$M_1 = 2$$ is the only possible solution.

For the induction step, suppose $M_n$ is a $n$-digit multiple of $2^n$, having only 2s and 3s as digits, say $M_n = k2^n$. Now consider the following two possibilities for $M_{n+1}$: $$ A = 2\cdot 10^{n} + M_n $$ and $$ B = 3 \cdot 10^n + M_n $$ both are multiples of $2^n$, namely $$ A = (2 \cdot 5^n + k)2^n, \qquad B = (3 \cdot 5^n + k)2^n $$ if $2 \cdot 5^n +k$ is even, say $2m = 2\cdot 5^n+k$, then $$ A = 2m \cdot 2^n = m2^{n+1}$$ and we are done with $M_{n+1} = A$, otherwise, as $5^n$ is odd, $$ (2 \cdot 5^n+k) + 5^n = 3 \cdot 5^n + k$$ is even, and we are done with $M_{n+1} = B$.

Answer 2

For the induction step, suppose the result is true at $n=k$. We want to show it is true at $n=k+1$.

So by the induction assumption there is a $k$-digit number $W_k$ whose digits are $2$'s and/or $3$'s which is divisible by $2^k$. We want to show that there is a $(k+1)$-digit number $W_{k+1}$, using $2$'s and/or $3$'s, such that $W_{k+1}$ is divisible by $2^{k+1}$.

There are two cases to examine (i) $W_k$ is already divisible by $2^{k+1}$ and (ii) $W_k$ is not divisible by $2^{k+1}$.

In Case (i), to make $W_{k+1}$, put a $2$ in front of the decimal expansion of $W_k$.

In Case (ii), to make $W_{k+1}$ put a $3$ in front of the decimal expansion of $W_k$.

Why does this work? For Case (i), note that the $(k+1)$-digit number $N$ whose first digit is $2$ and whose other digits are $0$ is divisible by $2^{k+1}$, and $W_{k+1}=N+W_k$.

For Case (ii), if $W_k$ is not divisible by $2^{k+1}$, then it has remainder $2^k$ on division by $2^{k+1}$. So does the $(k+1)$-digit number $N$ whose first digit is $1$ and whose other digits are $0$. So $N+W_k$ is divisible by $2^{k+1}$.

In each part, we used the fact that the highest power of $2$ that divides the $(k+1)$-digit number whose first digit is $1$ and the rest $0$'s is $2^k$.

Added: We illustrate by a partial computation. Let $W_1=2$. This has remainder $2$ on division by $4$, so we use $W_2=32$. This has remainder $0$ on division by $8$, so we use $W_3=232$. This has remainder $8$ on division by $16$, so we use $W_4=3232$. This has remainder $0$ on division by $32$, so we use $W_5=23232$. And so on.