# A property of digital sum

I was working on a computer program and came up with an intuitive idea that reduces the program module by a considerable length . The idea is intuitive but I never came up with a proof.

Claim : For a natural number n , let S(n) denote the sum of digits of n in its decimal expansion. Prove that there exists a natural number k , such that S(S(S(.......(n))...)) [S composed k times] is a single digit number.

Any help with this proof will be appreciable.

## 2 Answers

Well this is very easy to see, because $$s(n) unless $$n$$ is a single digit number. So $$s(s(n))>s(n)$$ and so on, we get $$s(s(...s(n))...)<... as long as $$s(s(...s(n))...)$$ is not a single digit integer. So if you compose that very many times (enough times), you will reach a single digit number.

To prove $$s(n), simply use the base 10 expansion.

Suppose $$n$$ has $$d$$ digits. Then $$S(n) \le 9 \, d \,$$. For $$d \ge 3, 9d \,$$ will always have fewer than $$d$$ digits, i.e. if $$n$$ has three digits or more, then $$S(n)$$ will have fewer digits than $$n \,$$.

Thus the sequence $$n, S(n), S(S(n)), S(S(S(n))), \ldots$$ must reduce the number of digits at every step until one gets number with less than three digits, call it $$N$$.

If $$N$$ is a single-digit number, then we're done. If $$N$$ is a two-digit number, then $$S(N) \le 18$$, but then $$S(S(N)) \le 9$$, and again we're done.