Digit sum formula $n - 9 \sum_{i\ge1} \left \lfloor \frac{n}{10^i} \right \rfloor$

Question

Let $S(n)$ be the sum of digits of n

Prove that $S(n) = n - 9 \sum_{i\ge 1} \left \lfloor \frac{n}{10^i} \right \rfloor$ for all natural numbers n

I started with induction which works easily if $10$ doesn't divide $n+1$, because then $S(n+1)$ is just $S(n) + 1$.

However, if $10|(n+1)$ then $S(n+1)$ could be anything. Moreover, I have no idea how to use that fact. If I write e.g. $n = 10k + 9$ then $\sum_{i\ge1} \left \lfloor \frac{10k+10}{10^i} \right \rfloor$ = $\sum_{i\ge1} \left \lfloor \frac{k+1}{10^{i-1}} \right \rfloor$ and I don't know how to proceed

Answer 1

Using strong induction, assume for all $n = 1,2, \ldots, k$, the sum of digits formula holds:

$$S(n) = n - 9\sum_{i\ge 1} \left\lfloor\frac n{10^i}\right\rfloor$$

The induction step would be to prove that $S(k+1)$ follows the same formula.

For the cases that $10\mid (k+1)$, let $k+1 = 10q$, (and so $1\le q \le k$)

$$\begin{align*} S(k+1) &= S\left(\frac{k+1}{10}\right)\\ &= S(q)\\ &= q - 9\sum_{i\ge 1} \left\lfloor\frac q{10^i}\right\rfloor\\ &= \frac{k+1}{10} - 9 \sum_{i\ge 1} \left\lfloor\frac {(k+1)/10}{10^i}\right\rfloor\\ &= 10\cdot\frac{k+1}{10}-9\cdot\frac{k+1}{10} - 9 \sum_{j\ge 2} \left\lfloor\frac {k+1}{10^j}\right\rfloor && (j=i+1)\\ &= (k+1) - 9 \sum_{j\ge 1} \left\lfloor\frac {k+1}{10^j}\right\rfloor\\ &= RHS \end{align*}$$

For the other cases that $10\not\mid(k+1)$, OP already mentioned in the question that $S(k+1) = S(k)+1$.

---

It is possible to merge the two cases with a slight change, by also proving the base case $n=0$ and including it into the assumption.

For the $n=k+1$ case, let $k+1 = 10q + r$, where $q = \left\lfloor \dfrac{k+1}{10}\right\rfloor$ and $r=(k+1)\bmod 10$.

$$\begin{align*} S(k+1) &= S(q) + r\\ &= q - 9\sum_{i\ge 1} \left\lfloor\frac q{10^i}\right\rfloor + r\\ &= q - 9\sum_{i\ge 1} \left\lfloor\frac {10q/10}{10^i}\right\rfloor + r\\ &= 10q - 9\cdot \frac{10q}{10} - 9\sum_{j\ge 2} \left\lfloor\frac {10q}{10^j}\right\rfloor + r&&(j=i+1)\\ &= 10q - 9\sum_{j\ge 1} \left\lfloor\frac {10q}{10^j}\right\rfloor + r\\ &= 10q+r - 9\sum_{j\ge 1} \left\lfloor\frac {10q}{10^j} + \frac{r}{10^j}\right\rfloor\\ &= (k+1) - 9\sum_{j\ge 1} \left\lfloor\frac {k+1}{10^j}\right\rfloor\\ &= RHS \end{align*}$$

Answer 2

Let $n$ be given and let $10^k$ be the largest power of $10$ that divides $n+1$. Then we have: $$ n=a+10^k d-1 $$ where $a$ is divisible by $10^{k+1}$ and $d\in\{1, 2,\cdots,9\}$. Now clearly: $$ S(n)=S(a)+S(10^k d-1) $$ similarly we have: $$ S(n+1)=S(a)+S(10^k d) $$ This shows that it suffices to focus on the latter part, so all you need is success for the induction step with $n+1=10^k d$. Thus we check: $$ \begin{align} 10^k d-9\sum_{i\geq 1}\left\lfloor\frac{10^k d}{10^i}\right\rfloor &=d\left(10^k-9(1+10+...+10^{k-1})\right)\\ &=d\left(10^k-(10^k - 1)\right)\\ &=d\\ &=S(10^k d) \end{align} $$ which is all we need to take care of all the steps in your original induction that were not covered.

Answer 3

Let $$n=\sum_{k=0}^m \lambda_k\cdot 10^k$$ Then $$S(n)=\sum_{k=0}^m \lambda_k$$ and $$\bigg\lfloor \frac{n}{10^i} \bigg\rfloor=\sum_{k=0}^{m-i}\lambda_{k+i}\cdot 10^k$$ So we are proving that: $$\sum_{k=0}^m \lambda_k\cdot 10^k-\sum_{k=0}^m \lambda_k=9\sum_{i=1}^m \bigg(\sum_{k=0}^{m-i}\lambda_{k+i}\cdot 10^k\bigg)$$

It seems quite nice from here.