Basis Representation Theorem

From ProofWiki

This article was Proof of the Week between 10 January 2010 and 18 February 2010.

[edit] Theorem

Let $b \in \Z: b > 1$ .

For every $n \in \Z_+$ , there exists one and only one sequence $\left \langle {r_k} \right \rangle_{0 \le k \le m}$ such that:

$n = \sum_{j = 0}^k r_j b^j$ ;
$\forall j \in \left[{0 \, . \, . \, k}\right]: r_j \in \N_b$ ;
$r_k \ne 0$ .

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 $s_b \left({n}\right)$ be the number of ways of representing $n$ to the base $b$ .

We need to show that $s_b \left({n}\right) = 1$ always.

Now, it is possible that some of the $r_i = 0$ in a particular representation. So we may exclude these terms, and it won't affect the representation.

So, suppose:

$n = r_k b^k + r_{k-1} b^{k-1} + \cdots + r_t b^t$

where $r_k \ne 0, r_t \ne 0$ .

Then:

$n - 1$	$=$	$r_k b^k + r_{k - 1} b^{k - 1} + \cdots + r_t b^t - 1$
	$=$	$r_k b^k + r_{k - 1} b^{k - 1} + \cdots + \left({r_t - 1}\right) b^t + b^t - 1$
	$=$	$r_k b^k + r_{k - 1} b^{k - 1} + \cdots + \left({r_t - 1}\right) b^t + \sum_{j = 0}^{t - 1} {\left({b - 1}\right) b^j}$	Sum of Geometric Progression

from the identity $\sum_{j = 0}^{n - 1} x^j = {\frac {x^n - 1} {x - 1}}, x \ne 1$ .

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 $s_b \left({n}\right) \le s_b \left({n - 1}\right)$ .

Note that this holds even if $n$ has no representation at all, because if this is the case, then $s_b \left({n}\right) = 0 \le s_b \left({n - 1}\right)$ .