A property of digital sum

Question

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 $$ \underbrace { S \bigg( S \Big( S \big( \dots S } _ { k \text { times} } ( n ) \big) \dots \Big) \bigg) $$ is a single digit number.

Any help with this proof will be appreciable.

Answer 1

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.

Answer 2

Well this is very easy to see, because $s(n)<n$ unless $n$ is a single digit number. So $s(s(n))>s(n)$ and so on, we get $s(s(...s(n))...)<...<s(s(n))<s(n)<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)<n$, simply use the base 10 expansion.