Elegance and Regret

I didn’t do any trigonometry today, but instead read more of Steven Strogatz’s The Joy of X and worked on the propositions about digit sums that I found in my notebook.

The most interesting tidbit from The Joy of X was Strogatz’s comment regarding a particular proof of the Pythagorean Theorem that, “The proof does far more than convince; it illuminates. That’s what makes it elegant.” That caught my attention and had me wondering whether all elegant proofs must be illuminating. I haven’t come to a conclusion yet.

To be illuminating is certainly not the only requirement for an elegant proof. The main proposition I worked on today was “the sum of the digits of any multiple of 9 is also a multiple of 9.” I came up with the outline of a proof by induction, the meat of which was a description of what happens to the digit sum when you add 9 to any natural number. It was full of cases and loops and was decidedly not elegant. I do think it gave a good sense of what was happening, though, and it could have been reworked to prove the general theorem that, in base $n$, the digit sum of any multiple of $n-1$ is also a multiple of $n-1$.

I was sure there must be a better proof, however, and I ended up searching for guidance on the Internet. I regret that, as I would rather have discovered the answer I found for myself. I did get to generalize it, at least, since it applied only to two-digit numbers. I’m not sure I would say that the result is illuminating. I don’t think it reveals why the theorem is true, except in as much as “why” is that 9 is one less than the base of the number system being used. It is simple, though. Does that make it elegant?

---

Proposition: For all $n\in\mathbb{N}$, the digit sum of $9n$ is a multiple of 9.

When $n$ is a natural number, $9n = 10^md_m+10^{m-1}d_{m-1}+…+10d_1+d_0$, where $d_m, d_{m-1},…,d_1, d_0$ are the digits of $9n$, in order.

$$10^md_m+10^{m-1}d_{m-1}+…+10d_1+d_0=$$ $$\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]+\left[d_m+d_{m-1}+…+d_1+d_0\right]$$

Thus, $$d_m+d_{m-1}+…+d_1+d_0=9n-\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]\text{.}$$

Note that the left-hand side of the equation is the digit sum of $9n$.

Note also that, for any natural number $x$, $$10^x-1=\sum_{i=0}^{x-1}10^i(9)=9\sum_{i=0}^{x-1}10^i\text{.}$$

[For instance, $10^3-1=1000-1=999=9(111)$.]

Hence, because each term of the expression is a multiple of 9, $$9n-\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]=9p$$ for some integer $p$.

It follows that the digit sum of $9n$ is a multiple of 9 for all $n\in\mathbb{N}$.

---

This proof could also be rewritten to cover all bases. In addition, the same argument could be used to prove that, in base 10, the digit sum of any multiple of three is also a multiple of three.

(And it occurs to me as I write this that you could also use it to prove the analogous fact, in base $n$, for any factor of $n-1$. That’s very cool and makes me feel like I have come up with something worthwhile on my own today.)