## Section1.1Positional 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.

### Definition1.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.