Skip to main content

Section 1.1 Positional Notation

It is common for us to write numbers as finite sequences of digits. Here, we don't care about the actual symbol (like \(1, 2, \dots\)) we use for a digit but only that we have finitely many of them. So for now, we assume that we have \(\bbase\) many digits and, for the sake of simplicity, we identify them with the natural numbers \(0,\dots,\bbase-1\) where \(\bbase\) is called the base of a specific positional number system. In our daily lives we use base 10 systems, a binary computer uses a base 2 system.

Formally, a sequence of digits \(x\) of length \(n\) is an \(n\)-tuple of digits, i.e. an element of the set \(\{0,\dots,\bbase-1\}^n\text{.}\) To simplify the presentation, we write an \(n\)-tuple \((x_{n-1}, \dots, x_0)\) shortly as \(\bseq xn\text{.}\)

Up to now a sequence of digits is just a bunch of symbols and does not have a particular meaning. The following definition defines a function, called the unsigned interpretation that associates a natural number to each finite digit sequence.

Definition 1.1.1. Unsigned Interpretation of Digit Sequences.

\begin{equation*} \buintpb{\cdot}{\bbase}:\{0,\dots,\bbase-1\}^+\to\Nat\qquad \bseq xn\mapsto \sum_{i=0}^{n-1}x_i\bbase^i \end{equation*}

\(x_{n-1}\) is called the most significant digit and \(x_0\) the least significant digit.

Given two digit sequences \(\alpha=\bseq an\) and \(\beta=\bseq bm\text{,}\) we can concatenate them and denote this by juxtaposing them \(\alpha\beta=\bseq an\bseq bm\text{.}\) We abbreviate the digit sequence \(\underbrace{a\dots a}_n\) by \(a^n\text{.}\)

The definition of \(\buintpb{\cdot}{\bbase}\) matches our intuition and coincides with the way we use numbers in our daily life. However, we might be interested in demonstrating that indeed each natural can be represented by a digit sequence. This is established by the next lemma.

By induction over \(n\text{.}\)

  1. Base case \(n=1\).

    Let \(k\in\{0,\dots,B-1\}\text{.}\) Then, \(k\) is a digit itself and \(\buintpb kB=k\text{.}\)

  2. Induction step \(n\to n+1\).

    Consider a number \(k\in\{0,\dots,B^{n+1}-1\}\text{.}\) Let \(q\) be the maximal number such that there exists an \(r\) with \(k = q\cdot B^n+r\text{.}\) Because \(q\) is maximal \(q\in\{0,\dots,B-1\}\) and \(r\in\{0,\dots,B^n-1\}\text{.}\)

    By induction, there is a digit sequence \(\rho\) such that \(\buintpb\rho B=r\text{.}\) By Lemma 1.1.2 it holds that \(\buintpb{q\rho}B=k\text{.}\)

Figure 1.1.4. This figure gives some intuition for Lemma 1.1.3. A digit sequence of a base \(B\) can be seen as a path in a tree in which each inner node has \(B\) children. The path shown in bold is the number \(\buintpb{21}3=7\text{.}\) Each layer of tree edges corresponds to a position, less significant digits being further down. One can also see that using positional notation is very efficient because to represent a number \(n\) one only needs \(\lceil\log_B n\rceil\) many digits.

What is the difference between a \(B=1\) positional system and a \(B>1\) positional system?

By induction over \(n\text{.}\)

  1. Base case \(n=1\).

    Trivial.

  2. Induction step \(n\to n+1\).

    The induction hypothesis is \(2^{n-1}=1+\sum_0^{n-2}2^i\text{.}\) Adding \(2^{n-1}\) to each side gives the desired result.