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.