Prove that $m \equiv S_m \pmod 3$? I'm not very fluent in mathematical proofs. High School has, sadly, not taught me any kind of proof-theory. That's why I would like your help with my proof of 
$$m \equiv S_m \pmod  3.$$
where $S_m$ is the digit sum of $m$ and $\wedge$ is a logical-AND.
I'm going to use the very little that I know:  Mathematical induction.
Basis:
$$A(1): S_m = 1 \wedge m = 1$$
$$m \equiv S_m \pmod 3\quad \text{because}\quad 1 \equiv 1 \pmod 3$$
Inductive Step:
$$A(n)\colon m = n \land S_m = \sum_{k=0}^K m_k = (m_0 + m_1 + \ldots + m_K)$$
$$m \equiv S_m \pmod 3.$$ 
So then
$$A(n+1)\colon m = n+1 \wedge S_m = \sum\limits_{k=0}^{K'} m_k = (m_0 + m_1 + \ldots + m_{K'})$$
$$m \equiv S_m \pmod 3.$$
I'm having trouble at the step of $A(n+1)$ because I don't know how to actually prove that it's valid? Please note that $m_0, \ldots, m_M$ refers to the summation of the digits of the number $m$. I just didn't find any good documentation that showed how to depict that in mathematical terms. Feel free to correct!
 A: The best way to get the result is that to remember that writing $m=a_n...a_1a_0$ in base 10 is actually a shorthand for
$$
m=a_0+a_1\cdot10+...+a_n\cdot 10^n.
$$
Now it's enough to observe that $10^n\equiv1\bmod 3$ for all $n$ and thus
$$
m\equiv a_0+a_1+...+a_n \bmod 3.
$$
A: The reason this works is as follows:
$$10 = 9 + 1$$
modulo 3 this says that $10 = 1$.
Numbers like $3157$ really mean $3 \cdot 10^3 + 1 \cdot 10^2 + 5 \cdot 10 + 7$, so applying the previous congruence we get $3 \cdot 10^3 + 1 \cdot 10^2 + 5 \cdot 10 + 7 = 3 + 1 + 5 + 7$ modulo 3.

Now that we have a strong understanding of why the theorem is true let head toward a detailed proof.
Let us use the principle that all numbers can be written down in base 10, for example the sequence of digits $(3,6,8,4)$ represents the number $4863$ (and a technicality, the empty sequence represents $0$).
First let us define the interpretation from sequences to numbers as a recursive function:
$$ \begin{align}
\text{interp}() &= 0 \\
\text{interp}(ds,d) &= d + 10 \cdot \text{interp}(ds)
\end{align}$$
$$ \begin{align}
\text{digitalroot}() &= 0 \\
\text{digitalroot}(ds,d) &= d + \text{digitalroot}(ds)
\end{align}$$
We can now prove the theorem (that the interpretation of a number is equal to its digital root) by induction on the length of the number:
Base case $\text{interp}() = 0 = \text{digitalroot}()$.
Inductive case, assume that $\text{interp}(ds) = \text{digitalroot}(ds)$, we would like to now prove that $d + 10 \cdot \text{interp}(ds) = d + \text{digitalroot}(ds)$, cancelling d and reducing the 10 to a 1 we simply have the hypothesis, which is known to be true. That completes the proof.
A: I'm having a little trouble understanding your formatting/notation, but I am guessing that what you want to show is that $m = S_m$ (mod 3) where $S_m$ is the sum of the digits of the number $m$.  In the inductive, step, it looks like you are saying that $S_{n+1} = S_n + 1$.  This is not always true (e.g. it is true if $n = 23$ but not true if $n = 59$).  So you should consider the two cases where the last digit is not a 9 and where the last digit is a 9.  You'll easily see you get the same thing mod 3 and this will complete the proof.
A: HINT: It suffices to work $\rm\pmod 9. \;$ Put $\rm\; S_N := $ the sum of the decimal digits of $\rm N$.
Notice $\rm\;N = 10\: n + r \;\Rightarrow\; S_N = S_n + r \;\Rightarrow\; N - S_N  = n - S_n + 9 \: n$. 
Hence $\rm\; N - S_N \equiv n - S_n \pmod 9$ -- the inductive step.
SIMPLER: For  $\rm N = a_k 10^k + \;\cdots + 10\; a_1 + a_0 \;$ put $\rm\; P(N) = a_k X^k + \;\cdots+ a_1 \; x + a_0$.  
FACTOR THEOREM $\rm\;\Rightarrow\; X-1|P(X)-P(1) \;\Rightarrow\; 9|P(10)-P(1) \;\:$ i.e. $\rm\; 9|N - S_N$.  
So casting nines follows from the Factor Theorem purely by the polynomial form of radix notation.  
Yet another example of the power of polynomials!
