Prove that the Odometer Principle with base $\displaystyle b $ gives the representation $\displaystyle x_{n-1} \ldots x_{1}x_{0} $ for the natural number $\displaystyle N = x_{n-1}b^{n-1} + \cdots + x_{1}b + x_0 $.

Odometer Principle to find the successor of a natural number to base $\displaystyle b $: Start by considering the rightmost digit.

- If the digit we are considering is not $\displaystyle b-1 $, then replace it with the next digit in order, and terminate the algorithm.

- If we are considering a blank space (to the left of all digits) then write in it the digit $\displaystyle 1 $, and terminate the algorithm.

- If neither of the above holds then we are considering the digit $\displaystyle b-1 $. Replace it with the digit $\displaystyle 0 $, move one place to the left, and return to the first bullet point.

Proof. We use induction on $\displaystyle n $. For $\displaystyle n=0 $, $\displaystyle N = x_0 = x_0 $. Now suppose that for $\displaystyle n=k $, $\displaystyle N = x_{k-1}b^{k-1} + \cdots + x_{1}b + x_0 = x_{k-1} \ldots x_{1}x_{0} $. So now we look at $\displaystyle x_0 $ (the rightmost digit) and apply the Odometer Principle?