Don't understand an induction proof for odometer principle

149 Views Asked by At

Prove by induction that the Odometer Principle with base b does indeed give the representation $$\text{$x_{n-1}...x_1x_0$ for the natural number $N = x_{n-1}b^{n-1}+...+x_1b+x_0$} $$.enter image description here

So my question is, in the bracketed section of the image, how does one get from one line to the next?

3

There are 3 best solutions below

0
On BEST ANSWER

Hint: This follows from the formula

$$ 1 + x + \dots + x^{n-1} = \frac{x^n - 1}{x - 1} $$

which holds for any positive integer $n$ and $x \neq 1$.

You can prove this formula by doing the multiplication

\begin{align*} (1 + x + \dots + x^{n-1} )(x - 1) &= x^n + (x^{n-1} - x^{n-1}) + (x^{n-2} - x^{n-2}) + \dots + (x - x) - 1 \\ & = x^n - 1. \end{align*}

0
On

The term $(b-1)(b^{m-1}+...+1)$ is equal to $b^m-1$. Then you add the final $1$, so you get $b^m$.

0
On

$...... + x_nb^m + (b-1)(b^{m-1} + b^{m-2} + ..... + 1) +1 =$

$...... + x_nb^m + [b(b^{m-1} + b^{m-2} + ..... + 1) - (b^{m-1} + b^{m-2} + ..... + 1)] + 1=$

$...... + x_nb^m + [(b^{m} + b^{m-1} + ..... + b) - (b^{m-1} + b^{m-2} + ..... + 1)] + 1=$

$...... + x_nb^m + [b^m + b^{m-1} - b^{m-1} + b^{m-2} - b^{m-2} + ... + b - b -1] + 1=$

$...... + x_nb^m + [b^m -1] + 1=$

$...... + x_nb^m + b^m=$

$...... + (x_n + 1)b^m $

=====

The text is assuming that you are familiar with $(b-1)(b^{m-1} + .... + 1) = b^m -1$ and that you can do $x_mb^m + (b-1)(b^{m-1} + .... + 1) +1 = x_mb^m + (b_m -1) + 1 = (x_m +1)b^m$ in your head.