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

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 r_0 +r_1a + ... + r_{(n-1)}a^{n-1} \leq (a-1)(1 + a + ... + a^{(n-1)})