Solution Set 4: Part B

Benjamin Bakker Mathematics 25a Prof. Berger

October 17, 2003

B.1. Writing a number in base b. Let b ≥ 2 be an integer, and choose n ∈ ℕ.

(1) Show that one can write n = ∑_{k=0}^{ℓ} x_{k}b^{k} with x_{k} ∈ {0, 1, …, b − 1} and some ℓ ≥ 0 in exactly one way.

Solution. We prove the claim by induction on the highest power ℓ ∈ ℕ such that b^{ℓ} ≤ n. The only case in which there is no such ℓ is n = 0, where n = 0 is the unique expansion. For ℓ = 0, we have 1 ≤ n ≤ b−1, and so the unique expansion is trivially n = nb^{0}. If ℓ ≥ 1, assume the result for all ℓ′ < ℓ. If b^{ℓ} ≤ n < b^{ℓ+1}, so that 1 ≤ nb^{−ℓ} < b, there is a unique integer x_{ℓ} ∈ {1, …, b − 1} such that nb^{−ℓ} ∈ [x_{ℓ}, x_{ℓ} + 1) (that is, x_{k} = ⌊nb^{−ℓ}⌋). Thus, n − x_{ℓ}b^{ℓ} < b^{ℓ}, and so by hypothesis there is a unique expansion n − x_{ℓ}b^{ℓ} = ∑_{k=0}^{ℓ′} x_{k}b^{k} for some ℓ′ < ℓ. Defining x_{k} = 0 for k > ℓ′ and k ≠ ℓ, the unique expansion of n is n = ∑_{k=0}^{ℓ} x_{k}b^{k}. □

(2) Let x ∈ [0, 1). Show that one can write x = ∑_{k=1}^{∞} x_{k}b^{−k} with x_{k} ∈ {0, 1, …, b − 1} in exactly one way, if we impose the additional condition that for every N ≥ 0, there is an n ≥ N such that x_{n} ≠ b − 1.

Solution. Let x_{0} = 0, and following the pattern in the above, inductively define y_{k−1} = ∑_{i=1}^{k−1} x_{i}b^{−i} (y_{0} = 0) to be the (k − 1)th partial sum and x_{k} = ⌊(x − y_{k−1})b^{k}⌋, k ≥ 1. Thus, for any k, x_{k}b^{−k} ≤ x − ∑_{i=0}^{k−1} x_{i}b^{−i} < (x_{k} + 1)b^{−k}, and

|x − y_{k}| < b^{−k}

The series y_{k} obviously converges since b ≥ 2 and b^{−k} ⟶ 0. If x_{k} = b − 1 for all k > m for some m, then the limit of the above series starting at m + 1 is b^{−m} (see below), and therefore x − y_{m} = b^{−m}, contrary to the above. Thus, we cannot have infinite strings of b − 1.

Assume that there are two such series, x = ∑_{k≥1} x_{k}b^{−k} = ∑_{k≥1} x′_{k}b^{−k}. Suppose that they first differ at the ℓth digit, and that the x′_{k} expansion has the higher digit. Then, since the difference of two convergent series converges to the difference of the limits,

0 = ∑_{k≥1}(x′_{k} − x_{k})b^{−k} = (x′_{ℓ} − x_{ℓ})b^{−ℓ} + ∑_{k>ℓ}(x′_{k} − x_{k})b^{−k}

⇒ (x′_{ℓ} − x_{ℓ})b^{−ℓ} = ∑_{k>ℓ}(x_{k} − x′_{k})b^{−k} < ∑_{k>ℓ}(b − 1)b^{−k}

where we have \underline{strict} inequality because of the added condition that there are no infinite strings of b − 1’s. But the series on the right is

∑_{k>ℓ}(b − 1)b^{−k} = (b − 1)b^{−ℓ−1} ∑_{k≥0} b^{−k} = b^{−ℓ−1} \frac{b − 1}{1 − b^{−1}} = b^{−ℓ} ⇒ b^{−ℓ} < b^{−ℓ}

and we have a contradiction, so the expansion is unique. □

B.2. The digits of 2^{n}. Let log_{2} stand for the logarithm base 2: if x > 0, log_{2} x is the unique real number such that 2^{log_{2} x} = x.

(1) Prove that log_{2} 10 is irrational.

Solution. Suppose it was rational, log_{2} 10 = p/q for some p, q ∈ ℤ_{≥1}. Then 2^{p} = 10^{q} = 2^{q}5^{p}; if p > q ≥ 1 then 2 either divides 5 or 1, while if 1 ≤ p ≤ q, either 5 divides 1 or p = q = 1 ⇒ 2 = 10. All possibilities lead to a contradiction, so log_{2} 10 is irrational. □

(2) Show that there is a number n ≥ 1 such that when one writes 2^{n} in base 10, the first few digits are 12121976....

Solution. In other words, we must prove the existence of an integer n such that

12121976 × 10^{m} ≤ 2^{n} < 12121977 × 10^{m}
⟺ m log_{2} 10 + log_{2}(12121976) ≤ n < m log_{2} 10 + log_{2}(12121977)

for some positive integer m. We essentially proved in lecture (as a Corollary to Dirichlet’s Theorem) that the fractional part of the positive multiples of an irrational number are dense in (0, 1). By (1), − log_{2} 10 is irrational, so for x the midpoint of log_{2}(12121976) and log_{2}(12121977), and ϵ half of the difference between them, there exists an integer m ∈ ℤ_{≥1} such that |{−m log_{2}} − x| < ϵ. But {−m log_{2} 10} = 1 − {log_{2} 10}, and therefore for some positive integer n − 1 (I’m calling this n − 1 just so the answer is cleaner),

log_{2}(12121976) < 1 − (m log_{2} 10 − (n − 1)) < log_{2}(12121977)

2^{n} then begins with the digits 12121976 (and has m + 8 digits altogether). □

\underline{Note:} James Dowdell found that one such number is n = 4205827. The corresponding power, 2^{n}, has 1266081 digits that fill roughly 353 pages. This problem can be generalized; you can find a power of 2 whose base ten expansion begins with any string of digits you choose.

B.3. Lévy’s chords lemma. Let f : [0, 1] → ℝ be a continuous function such that f(0) = f(1) and choose q ∈ ℤ_{≥1}. Prove that there exists x ∈ [0, 1 − 1/q] such that f(x + 1/q) = f(x).

Solution (adapted from Eric Suh’s proof). Let g(x) = f (x + \frac{1}{q}) − f(x). Consider the values of g on the points n/q, with n ∈ {0, 1, …, q − 1}. The sum

∑_{n=0}^{q−1} g(n/q) = f(1/q) − f(0/q) + f(2/q) − f(1/q) + ⋯ + f(q/q) − f(1 − 1/q) = f (1) − f(0) = 0

vanishes by assumption. Thus, either g(n/q) = 0 for all such n, in which case x = 0 satisfies the desired condition, or for some m, n < q, g(m/q) > 0 and g(n/q) < 0 (assume m > n). By the intermediate value theorem, there is some x ∈ (\frac{n}{q}, \frac{m}{q}) ⊂ [0, 1 − \frac{1}{q}] such that g(x) = 0 ⇒

f (x + \frac{1}{q}) = f(x).

□