MthT 430 Notes Chapter 4b Binary Expansions and Graphs

Construction of the Binary Expansion by Recursion

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

We construct the binary expansion of x:

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

This is the statement the infinite series

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

converges to x.

Step 1. Divide the interval [0,[1/(2⁰)]) into the two halves [0,[1/(2¹)]) and [[1/(2¹)],[1/(2⁰)]).

If 0 ≤ x < [1/(2¹)], let

⎧ ⎪ ⎨ ⎪ ⎩ b1 = 0, s1 = 0.binb1, r1 = x − s1.

If [1/(2¹)] ≤ x < [1/(2⁰)], let

⎧ ⎪ ⎨ ⎪ ⎩ b1 = 1, s1 = 0.binb1, r1 = x − s1.

Then 0 ≤ r₁ < [1/(2¹)].

If r₁ = 0, for n > 1, define b_n = 0 and Stop! x = s₁ = 0._binb₁.

Suppose that Step 1. … Step k. have been completed so that b_j = 0 or 1 have been defined so that

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ sk = 0.binb1 …bk, rk = x − sk, 0 ≤ rk < 1 2k .

Step (k+1). Divide the interval [0,[1/(2^k)]) into the two halves [0,[1/(2^k+1)]) and [[1/(2^k+1)],[1/(2^k)]).

If 0 ≤ r_k < [1/(2^k+1)], let

⎧ ⎪ ⎨ ⎪ ⎩ bk+1 = 0, sk+1 = 0.binb1 …bk+1, rk+1 = x − sk+1.

If [1/(2^k+1)] ≤ r_k < [1/(2^k)], let

⎧ ⎪ ⎨ ⎪ ⎩ bk+1 = 1, sk+1 = 0.binb1 …bk+1, rk+1 = x − sk+1.

Then 0 ≤ r_k+1 < [1/(2^k+1)].

If r_k+1 = 0, for n > k+1, define b_n = 0 and Stop! x = s_k+1 = 0._binb₁ …b_k+1.

Remark. Note that

lim k → ∞  sk = lim k → ∞  (x − rk) = x.

---

File translated from T_EX by T_TH, version 4.04.
On 22 Aug 2014, 13:53.