1
$\begingroup$

if $n_1$ is a multiple of 9, take the sum of $n_1$'s digits. Let this sum = $n_2$, then sum $n_2$'s digits and repeat until $n_k = 9$.

How would I use induction to prove that $n_k = 9$ for large enough $k$

my attempt:

base case: $n_1 = r9$, where $r = 1$, then for $k = 1$, $n_k = 9$

I have trouble finding the induction hypothesis for this question, I do know that $9|n_1$ and $n_1 \equiv 0 (mod 9)$

$\endgroup$
2
  • $\begingroup$ Do you really need induction ? Using $10\equiv 1\mod 9$ is much easier. $\endgroup$
    – Peter
    Oct 20, 2016 at 15:57
  • $\begingroup$ Hint: if $n>9$, then the digit sum of $n$ is less than $n$. $\endgroup$
    – egreg
    Oct 20, 2016 at 16:04

1 Answer 1

1
$\begingroup$

Let n$_1$ = 9
We know that 9 = 0 (mod9)
Now, we add all the digits of n$_1$. This gives us 9 and 9 = 9.
Now, we consider the next case, i.e. n$_1$+n$_1$ = 18.
We also know that 18 = 0 (mod9)
Adding the numbers of 18, we get 9 again!
Now, we take the third case. i.e. n$_1$+n$_2$ = 27.
As we know, the sum of digits of n$_1$ are 9 and those of n$_2$ reach 9.
Therefore, we can say that n$_1$ + n$_2$ = 0 (mod 9) if n$_1$ and n$_2$ are factors of 9 (n$_1$ = 0 (mod9) & n$_2$ = 0 (mod9))
taking this whole to be the base case, we can say that the sum of digits of n$_n$ will reach 9 if n$_n$ = n$_a$ + n$_b$ where n$_a$ and n$_b$ are factors of 9.
H.P.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .