# Proof:Base b representation

For all and , there exists a sequence of digits satisfying .

Note that this proof contains an algorithm for finding the digits. Note also that The base b representation is unique.

Proof:
We prove the claim by strong induction on .

In the base case, we WTS must find a base b representation of 0. The natural choice might be to take the single digit . Then is a digit (since ), and clearly .

However, when using this proof as an algorithm, it is preferable to take the 'empty' sequence as the representation of 0; otherwise all numbers would have a leading 0. Alternatively, one could give a special case in the inductive step for when is already a digit.

For the inductive step, assume that every number less than has a base b representation. We wish to show that has one also.

We can find the digits by dividing by : the last digit is given by the remainder, and the rest of the digits are those of the quotient.

Formally, let and . Let be the base b representation of (which we know exists by the inductive hypothesis).

Let , and let . We have