<s>[INST] Show that $5\cdot10^n+10^{n-1}+3$ is divisible by 9 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.
 [/INST] 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)
</s>