Having proven $\displaystyle 1/(1-x) = 1 + x + x^2 + ... + x^{(n-1)} + x^n/(1-x)$ previously, for any number $\displaystyle a \geq 2$, set [tex]x = a[/math] in the above. Use the resulting formula to show that for any integers $\displaystyle r_0, r_1... r_{n-1}$ with $\displaystyle 0 \leq r < a$ that

$\displaystyle r_0 + r_1a + r_2a^2 + ... + r_{(n-1)}a^{(n-1)} < a^n$

Assuming P(n) is the above statement, assume P(k) is true. To prove induction it must be shown the P(k+1) is true.

The book gives the hint:

Note that $\displaystyle r_0 +r_1a + ... + r_{(n-1)}a^{n-1} \leq (a-1)(1 + a + ... + a^{(n-1)})$