TAOCP 1.2.3 Exercise 20

Exercise 20. ▶ [25] Dr. I. J. Matrix has observed a remarkable sequence of formulas:

$$9 \times 1 + 2 = 11, \ 9 \times 12 + 3 = 111, \ 9 \times 123 + 4 = 1111, \ 9 \times 1234 + 5 = 11111.$$

a) Write the good doctor’s great discovery in terms of the $\sum$-notation. b) Your answer to part (a) undoubtedly involves the number 10 as base of the decimal system; generalize this formula so that you get a formula that will perhaps work in any base $b$. c) Prove your formula from part (b) by using formulas derived in the text or in exercise 16 above.

Verified: yes
Solve time: 1m31s

Solution

a)

The observed identities are

$$ 9\cdot 1+2=11,\qquad 9\cdot 12+3=111,\qquad 9\cdot 123+4=1111,\qquad 9\cdot 1234+5=11111. $$

The decimal integer $123\cdots n$ can be written as

$$ \sum_{j=1}^{n} j,10^{,n-j}, $$

and the integer consisting of $n+1$ digits equal to $1$ is

$$ \sum_{j=0}^{n} 10^{j}. $$

Hence Dr. Matrix's discovery is

$$ 9\sum_{j=1}^{n} j,10^{,n-j}+(n+1) = \sum_{j=0}^{n}10^{j}, \qquad 1\le n\le 9. $$

b)

Replace the decimal base $10$ by an arbitrary base $b$. The natural generalization is

$$ (b-1)\sum_{j=1}^{n} j,b^{,n-j}+(n+1) = \sum_{j=0}^{n} b^{j}. \tag{1} $$

For this formula to represent numerals in base $b$, one must have $n+1<b$, since the digits $1,2,\ldots,n+1$ must all be valid base-$b$ digits.

c)

Let

$$ S=\sum_{j=1}^{n} j,b^{,n-j}. $$

Then

$$ bS=\sum_{j=1}^{n} j,b^{,n+1-j}. $$

Using the change of variable $k=j-1$, as in rule (b),

$$ bS=\sum_{k=0}^{n-1}(k+1)b^{,n-k}. $$

Therefore

$$ \begin{aligned} (b-1)S &=bS-S\ &=\sum_{k=0}^{n-1}(k+1)b^{,n-k} -\sum_{k=1}^{n}k,b^{,n-k}. \end{aligned} $$

Separate the boundary terms:

$$ \begin{aligned} (b-1)S &=b^{n} +\sum_{k=1}^{n-1}\bigl((k+1)-k\bigr)b^{,n-k} -n\ &=b^{n}+\sum_{k=1}^{n-1}b^{,n-k}-n. \end{aligned} $$

Since $n-k$ runs through the values $1,2,\ldots,n-1$, rule (b) gives

$$ (b-1)S = \sum_{j=1}^{n} b^{j}-n. $$

Adding $n+1$ to both sides yields

$$ (b-1)S+(n+1) = \sum_{j=1}^{n} b^{j}+1. $$

Since $1=b^{0}$,

$$ (b-1)S+(n+1) = \sum_{j=0}^{n} b^{j}. $$

Substituting back the definition of $S$,

$$ (b-1)\sum_{j=1}^{n} j,b^{,n-j}+(n+1) = \sum_{j=0}^{n} b^{j}. $$

By the geometric-series formula (14),

$$ \sum_{j=0}^{n} b^{j} = \frac{b^{,n+1}-1}{b-1}. $$

Hence the generalized identity may also be written as

$$ (b-1)\sum_{j=1}^{n} j,b^{,n-j}+(n+1) = \frac{b^{,n+1}-1}{b-1}. $$

This completes the proof.

∎

$$ \boxed{ (b-1)\sum_{j=1}^{n} j,b^{,n-j}+(n+1) = \sum_{j=0}^{n} b^{j} = \frac{b^{,n+1}-1}{b-1} } $$