# Thread: Odometer Principle

1. ## Odometer Principle

Prove that the Odometer Principle with base $b$ gives the representation $x_{n-1} \ldots x_{1}x_{0}$ for the natural number $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 $b$: Start by considering the rightmost digit.

• If the digit we are considering is not $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 $1$, and terminate the algorithm.

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

Proof. We use induction on $n$. For $n=0$, $N = x_0 = x_0$. Now suppose that for $n=k$, $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 $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.