3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Where do you get "By adding up all the multiples of $9$" from the problem? $\endgroup$ – Simply Beautiful Art Oct 6 '17 at 0:27
  • $\begingroup$ We have to add up all of n1 (which is a multiple of 9). Or am I misinterpreting something? Thank you for your reply! $\endgroup$ – sktsasus Oct 6 '17 at 0:28
  • 2
    $\begingroup$ 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$. $\endgroup$ – Simply Beautiful Art Oct 6 '17 at 0:29
  • $\begingroup$ 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? $\endgroup$ – Hamed Oct 6 '17 at 1:10
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 ...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.