Bounds for Integer Expressed in Base k

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z$ be an integer.

Let $k \in \Z$ such that $k \ge 2$.

Let $n$ be expressed in base $k$ notation:

$n = \displaystyle \sum_{j \mathop = 1}^s a_j k^j$

where each of the $a_j$ are such that $a_j \in \set {0, 1, \ldots, k - 1}$.


Then:

$0 \le n < k^{s + 1}$


Proof

As none of the coefficients $a_j$ in $\displaystyle \sum_{j \mathop = 1}^s a_j k^j$ is (strictly) negative, the summation itself likewise cannot be negative

Thus:

$0 \le n$

The equality is satisfied when $a_j = 0$ for all $j$.


We then have:

\(\displaystyle n\) \(=\) \(\displaystyle \sum_{j \mathop = 1}^s a_j k^j\)
\(\displaystyle \) \(\le\) \(\displaystyle \paren {k - 1} \sum_{j \mathop = 1}^s k^j\) as $a_j \le k - 1$ for all $j$
\(\displaystyle \) \(=\) \(\displaystyle \paren {k - 1} \dfrac {k^{s + 1} - 1} {k - 1}\) Sum of Geometric Sequence
\(\displaystyle \) \(=\) \(\displaystyle k^{s + 1} - 1\)
\(\displaystyle \) \(<\) \(\displaystyle k^{s + 1}\)

$\blacksquare$


Sources