Basis Representation Theorem

From ProofWiki
Jump to: navigation, search


Theorem

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


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

$(1): \quad \displaystyle n = \sum_{j \mathop = 0}^k r_j b^j$;
$(2): \quad \displaystyle \forall j \in \left[{0 \,.\,.\, k}\right]: r_j \in \N_b$;
$(3): \quad 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$.


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:

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


from the identity $\displaystyle \sum_{j \mathop = 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)$.


So this inequality implies the following:

$\forall m, n: s_b \left({m}\right) \le s_b \left({m - 1}\right) \le \ldots \le s_b \left({n + 1}\right) \le s_b \left({n}\right)$


From N less than M to the N‎ and the fact that $b^n$ has at least one representation (itself), we see:

$1 \le s_b \left({b^n}\right) \le s_b \left({n}\right) \le s_b \left({1}\right) = 1$


The entries at either end of this inequality are $1$, so all the intermediate entries must also be $1$.

So $s_b \left({n}\right) = 1$ and the theorem has been proved.

$\blacksquare$


Comment

So, once we have chosen a base $b > 1$, we can express any positive integer $n$ uniquely as:

$\displaystyle n = \sum_{j \mathop = 0}^k {r_j b^j}: r_0, r_1, \ldots, r_k \in \left\{{0, 1, \ldots, b-1}\right\}$


Then we can write $\displaystyle n = \sum_{j \mathop = 0}^m {r_j b^j}$ as:

$\left[{r_m r_{m-1} \ldots r_2 r_1 r_0}\right]_b$


Also see


Sources