How to prove by induction that $10^n = 3m+1$

Question

Let $n∈ℕ_0$ and $m∈ℕ_0$. Show that $10^n = 3m+1$.

You can clearly see that for $n=0$, $m=0$ and $n=1$, $m=3$ and $n=2$, $m=33$ ... $n$ is the number of how many times a 3 is added to $m$ like $n=5$, then $m$ has to be $33333$ (five three's). But how to show that by induction? I always have problem to show something in a correct mathematical way...

Answer 1

To proceed by induction we have

• base case: $n=0 \implies 10^0=1=3\cdot 0+1$
• induction step: assume $10^n=3m+1$ true (Ind. Hyp.) we want to show that $10^{n+1}=3s+1$

then we have

$$10^{n+1}=10\cdot 10^n \stackrel{Ind. Hyp.}= 10 \cdot (3m+1)=$$$$=30m+10=30m+9+1=3(10m+3)+1=3s+1$$

Answer 2

You don't need induction for this:$$10^n-1=(9+1)^n-1=9^n+\binom n19^{n-1}+\binom n29^{n-2}+\cdots+\binom n{n-1}9,$$which is a multiple of $3$.

Answer 3

Hint

$$10^{n+1}=10 \cdot 10^n =10 \cdot (3m+1)=30 m+10= 3\cdot (10 m+3)+1$$

Answer 4

You can prove it also like this (without induction)

$$10^k-1 = (10-1)(\underbrace{10^{k-1}+10^{k-2}+...+10+1}_m)=9m$$

so you easyl get a stronger result, that is $$10^k=9m+1$$