Binary Expansion Arguments
Consider the following problem:
1.
Let f(x) be a function such that
•
domainf = [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!
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 x1 = 0, b1 = 0, s1 = 0.binb1.
If YES, let x1=x, b1 = 1, s1 = 0.binb1 = 0.bin1. In
both cases, for x1 ≤ x < 1, s1 ≤ f(x1) ≤ f(x) ≤ s1 + [1/2].
Next divide the interval [s1,s1 + [1/2]) into two
parts [0.binb10,0.binb11) and
[0.binb11,s1 + [1/2]).
Ask the question:
Is there an x ∈ [x1,1) such that f(x) ≥ s1 + [1/(22)] = 0.binb11?1
If NO, let x2 = x1, b2 = 0, s2 = 0.binb1b2.2 If
YES, let x2 = x, b1 = 1, s2 = 0.binb1b2 = s1 +[1/(22)]. Then for x2 ≤ x < 1, s2 ≤ f(x2) ≤ f(x) ≤ s2 + [1/(22)].
If x1, …, xn, b1, …bn, sn=0.binb1…bn have been constructed so that for xn ≤ x < 1, sn ≤ f(xn) ≤ f(x) ≤ sn + [1/(2n)],
Ask the
question: Is there an x ∈ [xn,1) such that
f(xn+1) ≥ sn + [1/(2n+1)] = 0.binb1…bn1?
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 xn ≤ x < 1,
sn ≤ f(x) ≤ L ≤ sn +
1
2n
and
0 ≤ L − f(x) <
1
2n
.
Footnotes:
1Thinking about this later,
I noticed that s1 + [1/(22)] is the midpoint of the new interval under consideration.
2In this case x2 = x1 and s2 = s1.
File translated from
TEX
by
TTH,
version 4.04. On 22 Aug 2014, 13:59.
