Basic Rhythms
Problem
Notice the following pattern, written in base 10:
$$ \begin{eqnarray} 987654321&=&8\times 123456789 &+&9\\ 98765432&=&8\times 12345678 &+&8 \\ 9876543&=&8\times 1234567 &+&7 \\ 987654&=&8\times 123456 &+&6\\ &\vdots & \\ 9&=&8\times 1&+&1 \end{eqnarray} $$
This patterns also holds in bases other than $10$. For example, in base $4$ we have $321 = 2 \times 123 + 3 $, and so on.
Why is this the case?
Getting Started
All the results can be checked by calculation. For an explanation and proof it is most efficient to use a general method that works for all bases. Moreover algebra reveals the structure that is obscured when using particular numbers to check special cases. Writing $b$ for the base then each expression can be written in terms of $b$ and, by collecting like terms in the expression, or equating the powers of $b$, it can be shown that each expression holds. All that is required is some care over the algebraic manipulation.
Student Solutions
| $987654321$ | $=$ | $8$ | $\times$ | $123456789$ | $+$ | $9$ |
| $98765432$ | $=$ | $8$ | $\times$ | $12345678$ | $+$ | $8$ |
| $9876543$ | $=$ | $8$ | $\times$ | $1234567$ | $+$ | $7$ |
| $987654$ | $=$ | $8$ | $\times$ | $123456$ | $+$ | $6$ |
| ... | ||||||
| $9$ | $=$ | $8$ | $\times$ | $1$ | $+$ | $1$ |
Saul Foresta explained as follows why this pattern holds in the decimal system and in other number systems using bases other than base $10$:
I generalized the problem for any base $n$ and any number of digits $r$ where $r$ can be anywhere from $1$ to $(n - 1)$.
Then after rewriting both sides of the equality given in the problem using sigma notation I arrived at the following:
$$ {\sum_{k=1}^r (n-k)n^{r-k}} = {{(n-2)\sum_{k=1}^r kn^{r-k} + r}} $$
In each summation $k$ stands for the $k$th digit of the number we're dealing with, reading from left to right. For example, in the number $9876$, $k$ ranges from $1$-$4$, where $9$ is $k=1$, $8$ is $k=2$, and so on.
So all I need to do in order to prove that this pattern holds is show that the left side of this equality does indeed equal the right side. Taking the terms like $8 \times123456789$, that is
$$ (n-2)\sum_{k=1}^r kn^{r-k} $$
over to the left hand side, we will prove that this expression is equal to $r$.
[(n-1)n r-1 + (n-2)n r-2 + (n-3)n
r-3 + ... + (n-r)] - (n-2)[n r-1 + 2n
r-2 + 3n r-3 + ... + r] =
[n r - n r-1 + n r-1 - 2n
r-2 + n r-2 - 3n r-3 + ...+ n - r]
- [n r - 2n r-1 + 2n r-1 - 2.2n
r-2 + ... + (n-2)r]
The coefficient of $n^{r-k}$ on this left hand side is $[1-k] - [k+1-2k] = 0$ for
$ ( 1 \le k \le r-1) $
and the coefficient of $n^r$ is also $0$.The coefficient of $n^0$ is $[-r] - [-2(r)] = r$ and hence this expression is equal to $r$ as required.