Proof: Basis Representation Theorem

[buffordboy23]

I had a question about the following theorem.

Basis Representation Theorem: Let k be any integer larger than 1. Then, for each positive integer n, there exists a representation

n = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s}

where a_{0} \neq 0, and where each a_{i} is nonnegative and less than k. Furthermore, this representation of n is unique; it is called the representation of n to base k.


Proof: Let b_{k}\left(n\right) denote the number of representations of n to the base k. We must show that b_{k}\left(n\right) always equals 1.

Suppose that

n = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t}

where neither a_{0} nor a_{s-t} equals zero. Then

n - 1 = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t} - 1 = a_{0}k^{s} + a_{1}k^{s-1} + ... + \left(a_{s-t} - 1\right)k^{t} + k^{t} - 1 = a_{0}k^{s} + a_{1}k^{s-1} + ... + \left(a_{s-t} - 1\right)k^{t} + \sum_{j=0}^{t-1} \left(k - 1\right)k^{t}

Thus we see that for each representation of n to the base k, we can find a representation of n-1. Consequently,

b_{k}\left(n\right) \leq b_{k}\left(n-1\right)


Question: In the previous line, why is there a "less than or equal to" sign rather than an "equal" or "greater than or equal to" sign?

 

[CRGreathouse]

Thus we see that for each representation of n to the base k, we can find a representation of n-1. Consequently,

b_{k}\left(n\right) \leq b_{k}\left(n-1\right)


Question: In the previous line, why is there a "less than or equal to" sign rather than an "equal" or "greater than or equal to" sign?

Each b_k representation has at least one associated b_k-1 representation, but there may be b_k-1 representations we don't know about. If there were U >= 0 such unknown representations (in fact U = 0, but we don't know that), then b_k + U = b_k-1, so b_k <= b_k-1.

 

[buffordboy23]

Thanks CRGreathouse.

This is clear now. When first reading the proof, it seemed obvious that U = 0, but this was the flaw in my thinking. So we could use the "equals" sign but only if we first show that U = 0, which is more work than is necessary.

 

[ppd]

Thanks so much! This was really puzzling me too.