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*}
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.
\(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{.}\)
Lemma 1.1.2.
Let \(\alpha=\bseq an\) and \(\beta=\bseq bm\) be two digit sequences. Then \(\buintpb{\alpha\beta}{\bbase}=\buintpb{\alpha}{\bbase}\cdot\bbase^m+\buintpb{\beta}{\bbase}\)
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.
Lemma 1.1.3.
Let \(B\) be greater than one and \(n\) greater than zero. For each natural number \(k\in\{0,\dots,B^n-1\}\) there is a digit sequence \(\alpha\) of length \(n\) such that \(\buintpb\alpha B=k\)
Proof.
By induction over \(n\text{.}\)
-
Base case \(n=1\).Let \(k\in\{0,\dots,B-1\}\text{.}\) Then, \(k\) is a digit itself and \(\buintpb kB=k\text{.}\)
-
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{.}\)
Checkpoint 1.1.5. Base 1.
What is the difference between a \(B=1\) positional system and a \(B>1\) positional system?
Lemma 1.1.6.
\(2^n=1+\sum_0^{n-1}2^i\)
Proof.
By induction over \(n\text{.}\)
-
Base case \(n=1\).Trivial.
-
Induction step \(n\to n+1\).The induction hypothesis is \(2^{n}=1+\sum_0^{n-1}2^i\text{.}\) Adding \(2^{n}\) to each side gives the desired result.
