MthT 430 Notes Chapter 6a Binary Expansions and Arguments

Real Numbers and Binary Expansions

The real numbers in R are identified with points on a horizontal line. For the time being, we will identify a real number x with a decimal expansion .

•

Every decimal expansion represents a real number x:

x = ±N.d1d2…, dk ∈ {0,1, ... ,9}.

This is the statement that every infinite series of the form

d1 10−1 + d2 10−2 + …,     dk ∈ {0,1, ... ,9},

converges.

Just as well we could identify a real number x with a binary expansion .

•

Every binary expansion represents a real number x:

x = ±N.binb1b2…, bk ∈ {0,1}.

This is the statement that every infinite series of the form

b1 2−1 + b2 2−2 + …,     bk ∈ {0,1},

converges.

A demonstration of a correspondence between the binary expansion and a point on a horizontal line was given in class.

Constructing the Binary Expansion

Let x be a real number, 0 ≤ x < 1.

We divide [0,1) into two half-open intervals, [0,[1/2]) and [[1/2],1).

Notice, that in binary notation we may write the two intervals respectively as [0, 0._bin1) and [0._bin1,1).

If x is in the left interval, x = 0 + 0·2⁻¹ + …, so we let b₁ = 0, s₁ = 0._binb₁, so that

x = 0.bin0 + … = s1 + r1,

where

0 ≤ r1 < 2−1.

If x is in the right interval, x = 0 + 1·2⁻¹ + …, so we let b₁ = 1, s₁ = 0._binb₁, so that

x = 0.bin1 + … = s1 + r1,

where

0 ≤ r1 < 2−1.

We formalize the process by saying

b1 = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0, 0 ≤ x < 1 2 , 1, 1 2 ≤ x < 1, s1 = 0.binb1 = b1·2−1, x = s1 + r1, 0 ≤ r1 < 2−1.

If the first remainder r₁ is 0, that is x = 0 or x = [1/2], STOP; x = s₁ and the binary expansion of x has been found.

If r₁ ≠ 0, we apply a similar process to r₁ = x − s₁ to find the second binary digit in the expansion of x. Let r₁^* = 2¹ ·r₁. Once again divide [0,1) into the two half-open intervals, [0,[1/2]) and [[1/2],1).

If r₁^* is in the left interval, x = 0 + b₁·2⁻¹ + 0·2⁻² + …; If r₁^* is in the right interval, x = 0 + b₁·2⁻¹ + 1·2⁻² + …, so we let b₁ = 1. This is same is saying that x is in the left or right half as the interval selected in step 1.

Thus

b2 = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0, 0 ≤ r1* < 1 2 , 1, 1 2 ≤ r1* < 1, s2 = 0.binb1 b2 = b1·2−1 + b2·2−2 x = s2 + r2, 0 ≤ r2 < 2−2.

If the second remainder r₂ is 0, STOP; x = s₂ and the binary expansion of x has been found. Otherwise continue!

The continuation may be defined by the Principle of Mathematical Induction (Recursion) so that if b_n, s_n = 0._binb₁…b_n, x = s_n + r_n, have been constructed so that 0 ≤ r_n < 2⁻ⁿ, let

rn* = 2n·rn, bn+1 = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0, 0 ≤ rn* < 1 2 , 1, 1 2 ≤ rn* < 1, sn+1 = 0.binb1 b2 …bn+1 = b1·2−1 + b2·2−2 + …+ bn+1·2−(n+1) x = sn+1 + rn+1, 0 ≤ rn+1 < 2−(n+1).

If the remainder r_n+1 is 0, STOP; x = s_n+1 and the binary expansion of x has been found. Otherwise continue!

What has been done: Given x, 0 ≤ x < 1, there is a nondecreasing sequence {s_n}_n=1^∞ of finite binary expansions such that 0 ≤ x − s_n < 2⁻ⁿ. Thus

lim n → ∞  sn = x.

---

File translated from T_EX by T_TH, version 4.05.
On 18 Sep 2014, 21:16.