1. Odometer Principle

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?

2. Clarity?

I am having trouble understanding the problem. What exactly is your question?

3. Originally Posted by Media_Man
I am having trouble understanding the problem. What exactly is your question?
The first sentence.

,

,

,

prove by induction that the odometer principle with base b

Click on a term to search for related topics.