A problem involving sum of digits of integers

contest-mathdecimal-expansionelementary-number-theory

Question: The sum of the digits of a natural number $n$ is denoted by $S(n)$. Prove that $S(8n) \ge \frac{1}{8}S(n)$ for each $n \in \mathbb N$.
[source:Latvia 1995]

At first I thought this problem can be solved using induction on the number of digits. Say without the leftmost digit (say $a_n$) of $n$ the number becomes $n'$. Then I tried to find some relation between $S(n)$ and $S(n')$ also $S(8n)$ and $S(8n')$. But that doesn't seem to be working in general.

I don't have much experience dealing with sums of digits, it seems somewhat random. Apart from any hint or solution in this problem, I am also interested in general strategies or any references in order to deal with such digit-sum problems. Thanks in advance.

Best Answer

For all natural numbers $a,b$ we have:

  • $S(10a)=S(a)$, and
  • $S(a+b)\le S(a)+S(b)$, with equality only when there is no carry when doing the grade school addition $a+b$.

A consequence of these is that for all natural numbers $n$ $$ \begin{aligned} S(125n)&=S(100n+20n+5n)\\ &\le S(100n)+S(20n)+S(5n)\\ &=S(n)+S(2n)+S(5n)\\ &=S(n)+S(n+n)+S(n+n+n+n+n)\\ &\le 8S(n). \end{aligned} $$ In other words, $$S(n)\ge\frac18 S(125n).$$

Plugging in $n=8m$ gives, for all natural numbers $m$, the inequality $$ S(8m)\ge\frac18 S(1000m)=\frac18 S(m). $$

Related Question