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^-1 + ¼, 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^-1 + ¼, 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^-1 + 0·2^-2 + ¼; If r₁^* is in the right interval, x = 0 + b₁·2^-1 + 1·2^-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^-n, 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^-n. Thus

lim n ® ¥  sn = x.

---

File translated from T_EX by T_TH, version 3.77.
On 12 Oct 2007, 10:35.