3.1: Binary Representations

Suppose $\left\{a_{n}\right\}_{n=1}^{\infty}$ is a sequence such that, for each $n=1,2,3, \ldots,$ either $a_{n}=0$ or $a_{n}=1$ and, for any integer $N,$ there exists an integer $n>N$ such that $a_{n}=0 .$ Then

$$0 \leq \frac{a_{n}}{2^{n}} \leq \frac{1}{2^{n}}$$

for $n=1,2,3, \dots,$ so the infinite series

$$\sum_{n=1}^{\infty} \frac{a_{n}}{2^{n}}$$

converges to some real number $x$ by the comparison test. Moreover,

$$0 \leq x<\sum_{n=1}^{\infty} \frac{1}{2^{n}}=1.$$

We call the sequence $\left\{a_{n}\right\}_{n=1}^{\infty}$ the binary representation for $x,$ and write

$$x=.a_{1} a_{2} a_{3} a_{4} \dots.$$

Exercise $\PageIndex{1}$

Suppose $\left\{a_{n}\right\}_{n=1}^{\infty}$ and $\left\{b_{n}\right\}_{n=1}^{\infty}$ are both binary representations for $x .$ Show that $a_{n}=b_{n}$ for $n=1,2,3, \ldots$.

Now suppose $x \in \mathbb{R}$ with $0 \leq x<1$. Construct a sequence $\left\{a_{n}\right\}_{n=1}^{\infty}$ as follows: If $0 \leq x<\frac{1}{2},$ let $a_{1}=0 ;$ otherwise, let $a_{1}=1 .$ For $n=1,2,3, \ldots,$ let

$$s_{n}=\sum_{i=1}^{n} \frac{a_{i}}{2^{i}}$$

and set $a_{n+1}=1$ if

$$s_{n}+\frac{1}{2^{n+1}} \leq x$$

and $a_{n+1}=0$ otherwise.

lemma $\PageIndex{1}$

With the notation as above,

$$s_{n} \leq x<s_{n}+\frac{1}{2^{n}}$$

for $n=1,2,3, \ldots$.

Proof

Since

$$s_{1}=\left\{\begin{array}{ll}{0,} & {\text { if } 0 \leq x<\frac{1}{2}} \\ {\frac{1}{2},} & {\text { if } \frac{1}{2} \leq x<1}\end{array}\right.$$

it is clear that $s_{1} \leq x<s_{1}+\frac{1}{2} .$ So suppose $n>1$ and $s_{n-1} \leq x<s_{n-1}+\frac{1}{2^{n-1}}$. If $s_{n-1}+\frac{1}{2 n} \leq x,$ then $a_{n}=1$ and

$$s_{n}=s_{n-1}+\frac{1}{2^{n}} \leq x<s_{n-1}+\frac{1}{2^{n-1}}=s_{n-1}+\frac{1}{2^{n}}+\frac{1}{2^{n}}=s_{n}+\frac{1}{2^{n}}.$$

If $x<s_{n-1}+\frac{1}{2^{n}},$ then $a_{n}=0$ and

$$s_{n}=s_{n-1} \leq x<s_{n-1}+\frac{1}{2^{n}}=s_{n}+\frac{1}{2^{n}}.$$

Q.E.D.

Proposition $\PageIndex{2}$

With the notation as above,

$$x=\sum_{n=1}^{\infty} \frac{a_{n}}{2^{n}}.$$

Proof

Given $\epsilon>0,$ choose an integer $N$ such that $\frac{1}{2^{n}}<\epsilon .$ Then, for any $n>N,$ it follows from the lemma that

$$\left|s_{n}-x\right|<\frac{1}{2^{n}}<\frac{1}{2^{N}}<\epsilon .$$

Hence

$$x=\lim _{n \rightarrow \infty} s_{n}=\sum_{n=1}^{\infty} \frac{a_{n}}{2^{n}}.$$

Q.E.D.

lemma $\PageIndex{3}$

With the notation as above, given any integer $N$ there exists an integer $n>N$ such that $a_{n}=0$.

Proof

If $a_{n}=1$ for $n=1,2,3, \dots,$ then

$$x=\sum_{n=1}^{\infty} \frac{1}{2^{n}}=1,$$

contradicting the assumption that $0 \leq x<1 .$ Now suppose there exists an integer $N$ such that $a_{N}=0$ but $a_{n}=1$ for every $n>N .$ Then

$$x=s_{N}+\sum_{n=N+1}^{\infty} \frac{1}{2^{n}}=s_{N-1}+\sum_{n=N+1}^{\infty} \frac{1}{2^{n}}=s_{N-1}+\frac{1}{2^{N}},$$

implying that $a_{N}=1,$ and thus contradicting the assumption that $a_{N}=0$. $\quad$ Q.E.D.

Combining the previous lemma with the previous proposition yields the following result.

Proposition $\PageIndex{4}$

With the notation as above, $x=. a_{1} a_{2} a_{3} a_{4} \ldots$.

The next theorem now follows from Exercise 3.1.1 and the previous proposition.

Theorem $\PageIndex{5}$

Every real number $0 \leq x<1$ has a unique binary representation.