MthT 430 Notes Chapter 6c Binary Expansions

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 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: Let

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 = s1 + 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 …bnbn+1 = sn + 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 sequence {s_n}_n=1^∞ of finite binary expansions such that 0 ≤ x − s_n < 2⁻ⁿ.

Binary Expansion Arguments

Consider the following problem:

1.

Let f(x) be a function such that

•

domain(f) = [0,1).

•

For all x (in [0,1)), 0 ≤ f(x) < 1.

•

The function f is increasing on [0,1).

Show that there is a number L, 0 ≤ L ≤ 1, such that

lim x → 1−  f(x) = L.

Hint: Construct a binary expansion for L.

A picture is helpful! See homepages.math.uic.edu/ jlewis/math430/chap6d.htm

To find the expansion for L, ask the question:

Is there an x ∈ [0,1) such that f(x) ≥ [1/2] = 0._bin1?

If NO, let x₁ = 0, b₁ = 0, s₁ = 0._binb₁. If YES, let x₁=x, b₁ = 1, s₁ = 0._binb₁ = 0._bin1. In both cases, for x₁ ≤ x < 1, s₁ ≤ f(x₁) ≤ f(x) ≤ s₁ + [1/2].

Next divide the interval [s₁,s₁ + [1/2]) into two parts [0._binb₁0,0._binb₁1) and [0._binb₁1,s₁ + [1/2]). Ask the question:

Is there an x ∈ [x₁,1) such that f(x) ≥ s₁ + [1/(2²)] = 0._binb₁1?¹

If NO, let x₂ = x₁, b₂ = 0, s₂ = 0._binb₁ b₂. If YES, let x₂ = x, b₁ = 1, s₂ = 0._binb₁b₂ = s₁ +[1/(2²)]. Then for x₂ ≤ x < 1, s₂ ≤ f(x₂) ≤ f(x) ≤ s₂ + [1/(2²)].

If x₁, …, x_n, b₁, …b_n, s_n=0._binb₁…b_n have been constructed so that for x_n ≤ x < 1, s_n ≤ f(x_n) ≤ f(x) ≤ s_n + [1/(2ⁿ)],

Ask the question: Is there an x ∈ [x_n,1) such that f(x_n+1) ≥ s_n + [1/(2ⁿ⁺¹)] = 0._binb₁…b_n1?

Then let

xn+1 = ⎧ ⎪ ⎨ ⎪ ⎩ xn, NO, x, YES, bn+1 = ⎧ ⎪ ⎨ ⎪ ⎩ 0, NO, 1, YES, sn+1 = 0.binb1 b2 …bn+1 = b1·2−1 + b2·2−2 + …+ bn+1·2−(n+1) For xn+1 ≤ x < 1,     sn+1 ≤ f(xn+1) ≤ f(x) ≤ sn+1 + 1 2n+1 .

Then

L = 0.b1b2…bn… = lim n → ∞  sn

since for all x, if x_n ≤ x < 1,

sn ≤ f(x) ≤ L ≤ sn + 1 2n

and

0 ≤ L − f(x) < 1 2n .

This shows that

lim x → 1−  f(x) = L.

Additional Arguments Constructing the Binary Expansion of the Number Sought

See homepages.math.uic.edu/ jlewis/mtht430/chap7b.htm

Footnotes: