# Definition:Basis Expansion

## Definition

### Positive Real Numbers

Let $x \in \R$ be a real number such that $x \ge 0$.

Let $b \in \N: b \ge 2$.

Let us define the recursive sequence:

- $\forall n \in \N: n \ge 1: \sequence {f_n} = \begin {cases} b \paren {x - \floor x} & : n = 1 \\ b \paren {f_{n - 1} - \floor {f_{n - 1} } } & : n > 1 \end{cases}$

Then we define:

- $\forall n \in \N: n \ge 1: \sequence {d_n} = \floor {f_n}$

It follows from the method of construction and the definition of the floor function that:

- $\forall n: 0 \le f_n < b$ and hence $\forall n: 0 \le d_n \le b - 1$
- $\forall n: f_n = 0 \implies f_{n + 1} = 0$ and hence $d_{n + 1} = 0$.

Hence we can express $x = \floor x + \displaystyle \sum_{j \mathop \ge 1} \frac {d_j} {b^j}$ as:

- $\sqbrk {s \cdotp d_1 d_2 d_3 \ldots}_b$

where:

- $s = \floor x$
- it is not the case that there exists $m \in \N$ such that $d_M = b - 1$ for all $M \ge m$.

(That is, the sequence of digits does not end with an infinite sequence of $b - 1$.)

This is called the **expansion of $x$ in base $b$**.

The generic term for such an expansion is a **basis expansion**.

It follows from the Division Theorem that for a given $b$ and $x$ this expansion is unique.

### Negative Real Numbers

Let $x \in \R: x < 0$.

We take the absolute value $y$ of $x$, that is:

- $y = \size x$

Then we take the **expansion of $y$ in base $b$**:

- $\size {s . d_1 d_2 d_3 \ldots}_b$

where $s = \floor y$.

Finally, the **expansion of $x$ in base $b$** is defined as:

- $-\sqbrk {s . d_1 d_2 d_3 \ldots}_b$

## Termination

Let the basis expansion of $x$ in base $b$ be:

- $\sqbrk {s \cdotp d_1 d_2 d_3 \ldots}_b$

Let it be the case that:

- $\exists m \in \N: \forall k \ge m: d_k = 0$

That is, every digit of $x$ in base $b$ after a certain point is zero.

Then $x$ is said to **terminate**.

## Recurrence

Let the basis expansion of $x$ in base $b$ be:

- $\sqbrk {s \cdotp d_1 d_2 d_3 \ldots}_b$

Let there be a finite sequence of $p$ digits of $x$:

- $\tuple {d_{r + 1} d_{r + 1} \ldots d_{r + p} }$

such that for all $k \in \Z_{\ge 0}$ and for all $j \in \set {1, 2, \ldots, p}$:

- $d_{r + j + k p} = d_{r + j}$

where $p$ is the smallest $p$ to have this property.

That is, let $x$ be of the form:

- $\sqbrk {s \cdotp d_1 d_2 d_3 \ldots d_r d_{r + 1} d_{r + 2} \ldots d_{r + p} d_{r + 1} d_{r + 2} \ldots d_{r + p} d_{r + 1} d_{r + 2} \ldots d_{r + p} d_{r + 1} \ldots}_b$

That is, $\tuple {d_{r + 1} d_{r + 2} \ldots d_{r + p} }$ repeats from then on, or **recurs**.

Then $x$ is said to **recur**.

## Also see

- The Existence of Base-N Representationâ€Ž for a rigorous proof that this expansion always exists and (except in a particular case) is unique.

- The Basis Representation Theorem for the equivalent theorem for integers.

- Results about
**basis expansions**can be found here.