Mathematical Induction question

Question

This question should be done using either strong induction or weak induction.

If $111$ is a multiple of $3$

$111 111 111$ is a multiple of $9$

$111 1111111111111111111111$(to $n$) is a multiple of $3^n$

Prove this using induction

Answer 1

Let $$\underbrace{111\cdots 111}_{3^{n} }=3^{n}k$$

Then $$\underbrace{111\cdots 111}_{3^{n+1} } = 3^{n}k\cdot (10^{3^{n+1}-3^{n}}+10^{3^{n}}+1)$$

We have $$10^{m}\equiv 1 \pmod 3$$

Therefore,

$$10^{3^{n+1}-3^{n}}+10^{3^{n}}+1\equiv 1+1+1=3\pmod 3$$

Hence $$\underbrace{111\cdots 111}_{3^{n+1} } $$ is divisible by $3^{n}\cdot 3=3^{n+1}$

Answer 2

HINT:

Observe that $\underbrace{11...11}_{r \text{ terms }}=\frac{10^r-1}9$ where integer $r\ge1$

Let the highest power of $3$ in $\underbrace{11...11}_{3^m \text{ terms }}=\frac{10^{3^m}-1}9$ be $n$

So, $P(m)=10^{3^m}-1=9\cdot 3^n \cdot b$ where $(b,3)=1$

So, $P(m+1)=10^{3^{m+1}}-1=(10^{3^m})^3-1=(3^{n+2}b+1)^3-1\equiv0\pmod{3^{n+3}}$

Now, $P(1)=999\equiv0\pmod {3^{1+1}}$