How would I prove the following by induction?

Let $n_1 > 0$ be a multiple of $9$. Suppose that we add up all the (base-10 digits) of $n_1$; denote this sum by $n_2$. Then add up all the digits of $n_2$ to get $n_3$, and all the digits of $n_3$ to get $n_4$, and so on. This produces a sequence of numbers $n_1, n_2, n_3, \dots , n_k,\dots$

Use induction to prove that $n_k = 9$ for all large enough $k$. When you write up your solution, clearly state your induction hypothesis.

So far, I have tried to write down the statements above in mathematical form but I am encountering a few problems. By adding up all the multiples of $9$, wouldn't I go to infinity as there are an infinite number of multiples of $9$. Also, how would I develop a base case and induction hypotheses when relating to sums?

Any help?

• Where do you get "By adding up all the multiples of $9$" from the problem? – Simply Beautiful Art Oct 6 '17 at 0:27
• We have to add up all of n1 (which is a multiple of 9). Or am I misinterpreting something? Thank you for your reply! – sktsasus Oct 6 '17 at 0:28
• No, it reads "we add up all the (base-10 digits) of $n_1$". For example, if $n_1=72$, then $n_2=7+2=9$. – Simply Beautiful Art Oct 6 '17 at 0:29
• Hint: Prove that $n_1$ is a multiple of 9 if and only if $n_2$ is a multiple of 9 and moreover that $n_1>n_2$. Do you see the induction now? – Hamed Oct 6 '17 at 1:10

Sketch of a proof:

Using x so as not to confuse with n in problem definition.

x_1 = 9 * 1 = 9 -> (multiple of 9)

x_2 = 9 * 2 = 18: 1 + 8 = 9 -> (multiple of 9)

x_3 = 9 * 3 = 27: 2 + 7 = 9 -> (multiple of 9)

.

.

.

assume:

x_k = 9 * k = ??: sum of x_k digits -> (multiple of 9)

then:

x_(k+1) = 9 * (k+1) = (9 * k) + 9 = x_k + 9 : sum of x_k digits + 9

                              = (multiple of 9) + 9 = (multiple of 9)


Clearly, for any multiple of 9, the sum of the digits making up that number

reduces to 9 (e.g. 999 reduces to 27 reduces to 9).

Hope this helps.

First, you want to get real clear on the claim you are trying to prove. I suggest:

"For every $n>0$ that is a multiple of $9$, when we set $n_1=n$ and go through the process as described, there is some $k$ such that $n_k=9$"

Second, think whether weak or strong induction would make more sense ...