MthT 430 Notes Chap 7b Hard Theorems - Proofs by Binary Expansion
MthT 430 Notes Chap 7b Hard Theorems - Proofs by Binary Expansion
For this discussion, we shall assume:

(P13-BIN) Binary Expansions Converge. Every binary expansion represents a real number x: every infinite series of the form
c1 2-1 + c2 2-2 + ¼+ ck 2-k + ¼,    ck Î {0,1},
converges to a real number x in [0,1] and write the binary expansion of x as
x
= .binc1 c2 ¼.
Continuous Functions on Intervals Have the Intermediate Value Property

Theorem 1. If f is continuous on [a,b] and f(a) < 0 < f(b), then there is some x in [a,b] such that f(x) = 0.
In numerical analysis, the following is known as finding the root of f(x) = 0 by the method of bisection .
We will show this result by constructing the binary expansion of a number x Î (a,b) such that f(x) = 0.
Without loss of generality, [a,b] = [0,1]. The rough idea is to ask: If there is such an x, is x in the left half or in the right half of [0,1], and then proceed by recursion (induction).
Let m1 = [1/2] be the midpoint of [0,1]. Ask the question: Is f(m1) < 0, = 0, or > 0.
Cases:
·
If f(m1) = 0, let x = m1 = 0.bin1. STOP! f(x) = 0 as desired.
·
If f(m1) < 0, the function changes sign on (m1, 1) so we look for the root on (m1, 1). Let
a1
= m1,
b1
= 1,
c1
= 1,
s1
= 0.binc1
= 0.bin1
= a1.
Note that
b1 - a1
= 1
21
 ,
f(a1) < 0
< f(b1).
·
If f(m1) > 0, the function changes sign on (0, m1) so we look for the root on (0, m1). Let
a1
= 0,
b1
= = m1
= 1
2
 ,
= a1 + 1
2
c1
= 0,
s1
= 0.binc1
= 0.bin0
= a1.
Note that
b1 - a1
= 1
21
 ,
f(a1) < 0
< f(b1).
We think of c1 as the first binary digit in the expansion of x.
Suppose that an, bn = an + [1/(2n)], sn = an = 0.binc1¼cn have been constructed so that
f(a1) < 0 < f(b1),
, let mn = an + [1/(2n+1)] = [1/2](an + bn). Ask the question: Is f(mn) < 0, = 0, or > 0.
Cases:
·
If f(mn) = 0, let x = mn = sn + [1/(2n+1)] = 0.binc1¼cn1. STOP! f(x) = 0 as desired.
·
If f(mn) < 0, the function changes sign on (mn, bn) so we look for the root on (mn, bn). Let
an+1
= mn,
bn+1
= bn,
cn+1
= 1,
s1
= 0.binc1¼cncn+1
= 0.binc1¼cn1
= an+1.
Note that
bn+1 - an+1
= 1
2n+1
 ,
f(an+1) < 0
< f(bn+1).
·
If f(mn) > 0, the function changes sign on (an,mn) so we look for the root on (an, mn). Let
an+1
= an,
bn+1
= mn,
cn+1
= 0,
s1
= 0.binc1¼cncn+1
= 0.binc1¼cn0
= an+1.
Note that
bn+1 - an+1
= 1
2n+1
 ,
f(an+1) < 0
< f(bn+1).
If the process does not stop, we have that, for all n,
f(sn) < 0 < f æ
è 		sn + 1
2n+1
 ö
ø 		.
Let
x
=
lim
n ® ¥ 
 sn
= 0.binc1c2¼cn¼.
We have that f(x) = 0 since
f(x)
=
lim
n ® ¥ 
 f(sn)
£ 0,
f(x)
=
lim
n ® ¥ 
 f æ
è 		sn + 1
2n+1
 ö
ø
³ 0.
The Bolzano-Weierstraß Theorem

Theorem (Bolzano-Weierstraß). Let {xn}n=1¥ be a sequence of points in. [0,1]. Then there is an x in [0,1] which is a limit point3 of the sequence {xn}n=1¥.
The proof will construct a binary expansion for x.
Now - either infinitely many terms of the sequence are 1, in which case x = 1 = 0.bin0 is the desired limit point OR
Ask the question: For infinitely many k, is it true that xk Î [0,[1/(21)])?
If YES, let
c1
= 0,
a1
= 0 = 0.bin0,
b1
= 1
2
= a1 + 1
21
 .
s1
= a1.
Then
b1 - a1
= 1
21
 ,
Infinitely many xk are in [a1,b1).
If NO, let
c1
= 1,
a1
= 1
2
 = 0.bin1,
b1
= 1 = 1.bin0
= a1 + 1
21
 .
s1
= a1.
Then
b1 - a1
= 1
21
 ,
Infinitely many xk are in [a1,b1).
Now continue, ¼
x
=
lim
n ® ¥ 
 sn
=
lim
n ® ¥ 
 æ
è 		sn + 1
2n
 ö
ø
Note that 0 £ x - sn = |x - sn| £ [1/(2n)].

Footnotes:

3A point x is a limit point of the sequence if for every e > 0, infinitely many terms of the sequence are within e of x. Alternately, there is a subsequence which converges to x. A more informal idea is to say that infinitely many terms are as close as desired to x.

File translated from TEX by TTH, version 3.78.
On 24 Oct 2007, 09:26.