Basis Representation Theorem
From ProofWiki
[edit] Theorem
Let
.
For every
, there exists one and only one sequence
such that:
-
;
-
;
-
.
This unique sequence is called the representation of n to the base b, or, informally, we can say n is (written) in base b.
[edit] Proof
Let
be the number of ways of representing n to the base b.
We need to show that
always.
Now, it is possible that some of the ri = 0 in a particular representation. So we may exclude these terms, and it won't affect the representation.
So, suppose:
where
.
Then:
| n − 1 | = |
| ||||
| = |
| |||||
| = |
| Sum of Geometric Progression |
from the identity
.
Note that we have already specified that b > 1.
So for each representation of n to the base b, we can find a representation of n − 1.
If n has another representation to the base b, then the same procedure will generate a new representation of n − 1. Thus
.
Note that this holds even if n has no representation at all, because if this is the case, then
.
So this inequality implies the following:
From N less than M to the N and the fact that bn has at least one representation (itself), we see:
The entries at either end of this inequality are 1, so all the intermediate entries must also be 1.
So
and the theorem has been proved.
[edit] Comment
So, once we have chosen a base b > 1, we can express any positive integer n uniquely as:
Then we can write
as:

