Show that $5\cdot10^n+10^{n-1}+3$ is divisible by 9

Question

Prove by induction the following:

$5*10^n+10^{n-1}+3$ is divisible by 9

Base case: $n=1$ $5*10+10^{1-1}+3=5*10+10^0+3=50+1+3=54$

$9|54=6$

Inductive Hypothesis: If $k$ is a natural number such that $9|5*10^k+10^{k-1} +3$

Inductive step: Show that $S_k$ is true $\Rightarrow$ $S_{k+1}$ is true

$S_{k+1}$: $9|5*10^{k+1}+10^{k} +3$

$9|10(5*10^{k+1}+10^{k} +3)$

$9|5*10^{k+2}+10^{k+1} +10*3$

$9|5*(10^{k+1}*10^1)+(10^{k}*10^1) +(9+1)*3$

$9|5*(10^{k+1}*(9+1))+(10^{k}*10*(9+1)) +(9+1)*3$

$9|5(9*10^{k+1}+10^{k+1})+9*10^k+10^k+((9*3)+(1*3))$

This is were I am stuck for the last day try to figure out what move next would speed up the inductive proof as I have a feeling it can be finished up. Anyone help me see what I am unable to find.

Answer 1

The best way to show this kind of an equality, is to show that $S_{k-1} - S_k$ is divisible by $9$.

\begin{split} S_{k+1} - S_k & = (5 \times 10^{k+1} + 10^{k} + 3) - (5 \times 10^k + 10^{k-1} + 3)\\ & = 5(10^{k+1}-10^k) + (10^k-10^{k-1}) \\ & = 5\times 9 \times 10^k + 9 \times 10^{k-1} \\ & = 9 \times (5 \times 10^k + 10^{k-1}) \end{split}

Hence, $S_{k+1} = S_k + 9 \times (5 \times 10^k + 10^{k-1})$. Since $9|S_k$ and $9|9 \times (5 \times 10^k + 10^{k-1})$, it is clear that $9|S_{k+1}$. Hence, the induction is complete.

It is also nice to note that the pattern of numbers produced by $S_k$ go like $54$,$513$,$5103$,$51003$ etc. all of which have sum of digits the same i.e. $9$, so all are divisible by $9$ (this needn't be proved inductively at all)

Answer 2

Induction hypothesis: $$9|5\times10^k+10^{k-1}+3$$ Thus, $$9|10(5\times10^k+10^{k-1}+3)$$ $$9|5\times10^{k+1}+10^k+30$$ $$9|5\times10^{k+1}+10^k+3+27$$ But $9|27$. Hence, $$9|5\times10^{k+1}+10^k+3$$ which is what had to be shown.

Answer 3

Note that if for some $n \geq 1$ the proposition is true then $5\cdot 10^{n} + 10^{n-1} + 3 = 9k$ for some $k$; hence $$ 5\cdot 10^{n+1} + 10^{n} + 3 = 90k - 27. $$

Answer 4

Hint:$$5\cdot10^{n+1}+10^{n} +3=10\cdot5\cdot10^{n}+10\cdot10^{n-1}+30-27=$$ $$=10(5\cdot10^{n}+10^{n-1} +3)-3\cdot9$$

Answer 5

An integer is divisible by $3^k$ if and only if the sum of the digits is divisible by $3^k$. In this case, note the sum of the digits is always $9$!