Math 115. Slides from the Lecture of November 22

(More) Infinite Simple Continued Fractions

Throughout today’s class:

a_{0}, a_{1}, ⋯ ∈ ℤ and a_{i} > 0 for all i > 0 .

Lemma. Let θ = ⟨a_{0}, a_{1}, … ⟩ and θ_{1} = ⟨a_{1}, a_{2}, … ⟩. Then:

(a). θ ≥ a_{0} ,

(b). θ = a_{0} + \frac{1}{θ_{1}} ,

(c). θ_{1} > 1 , and (d). a_{0} = [θ] .

Theorem (Uniqueness). Let ⟨a_{0}, a_{1}, … ⟩ and ⟨b_{0}, b_{1}, … ⟩ be infinite simple continued fractions. If ⟨a_{0}, a_{1}, … ⟩ = ⟨b_{0}, b_{1}, … ⟩, then a_{i} = b_{i} for all i.

Proof. Induction on i. Let θ = ⟨a_{0}, a_{1}, … ⟩ = ⟨b_{0}, b_{1}, … ⟩. Then a_{0} = [θ] = b_{0} ; combining this with

a_{0} + \frac{1}{⟨a_{1}, a_{2}, … ⟩} = θ = b_{0} + \frac{1}{⟨b_{1}, b_{2}, … ⟩}

gives ⟨a_{1}, a_{2}, … ⟩ = ⟨b_{1}, b_{2}, … ⟩. Repeat to get a_{i} = b_{i} for all i by induction. □

This suggests that a procedure, similar to that for finding finite simple continued fractions, would be useful for finding infinite simple continued fractions (or at least initial finite sequences of their partial quotients a_{i}).

Summarizing (so far)

Last time we defined a function

f: {infinite integer sequences a_{0}, a_{1}, … with a_{i} > 0 for all i > 0 } ⟶ ℝ \ ℚ

given by

(a_{0}, a_{1}, …) ↦ ⟨a_{0}, a_{1}, … ⟩ .

Now we’ve shown that this function is injective.

Theorem (Existence). Let ξ ∈ ℝ be an irrational number. Then:

(a). there exists an integer sequence a_{0}, a_{1}, … with a_{i} > 0 for all i > 0 , and

irrational ξ_{0}, ξ_{1}, ⋯ ∈ ℝ, such that: (i)
⟨a_{0}, …, a_{i−1}, ξ_{i}⟩ = ξ  (*)
for all i ∈ ℕ; and (ii) ξ_{i} > 1 for all i > 0 .
(b). ⟨a_{0}, a_{1}, … ⟩ = ξ.

Proof. (a). By induction on n ∈ ℕ, we will construct a_{0}, …, a_{n−1} and ξ_{0}, …, ξ_{n} such that (*) holds for all i ≤ n.

Base case: If n = 0 , then no a_{i} need to be constructed, and we let ξ_{0} = ξ. Then (*) with i = 0 is ⟨ξ_{0}⟩ = ξ_{0} = ξ, so we’re done.

Inductive step: Assume that n > 0 , and that we have a_{0}, …, a_{n−2} ∈ ℤ and irrational ξ_{0}, …, ξ_{n−1} , such that a_{i} > 0 for all 0 < i ≤ n − 2 and (*) holds for all 0 ≤ i ≤ n − 1 .

Let a_{n−1} = [ξ_{n−1}] and ξ_{n} = \frac{1}{ξ_{n−1} − a_{n−1}} . Note that:

• ξ_{n} is irrational because ξ_{n−1} is,

• 0 < ξ_{n−1} − a_{n−1} < 1 ( ξ_{n−1} ≠ a_{n−1} because ξ_{n−1} is irrational),

• ξ_{n} > 1 ,

• ⟨a_{0}, …, a_{n−1}, ξ_{n}⟩ = ⟨a_{0}, …, a_{n−2}, a_{n−1} + 1/ξ_{n}⟩ = ⟨a_{0}, …, a_{n−2}, ξ_{n−1}⟩ = ξ; and

• a_{n−1} > 0 if n > 1 (because ξ_{n−1} > 1 if n > 1 ).

This proves (a).

(b). Let h_{n}, k_{n} ( n ≥ −2 ) be as before, and for all n ∈ ℕ let

r_{n} = \frac{h_{n}}{k_{n}} = ⟨a_{0}, …, a_{n}⟩ .

Let θ = lim_{n→∞} r_{n} = ⟨a_{0}, a_{1}, … ⟩. We need to show that θ = ξ.

For all n ≥ 2 let f_{n}: ℝ_{≥0} → ℝ be the function

f_{n}(x) = ⟨a_{0}, …, a_{n−1}, x⟩ = \frac{h_{n−1}x + h_{n−2}}{k_{n−1}x + k_{n−2}} .

Then

\begin{aligned}f′_{n}(x) & = \frac{d}{dx}(\frac{h_{n−1}x + h_{n−2}}{k_{n−1}x + k_{n−2}}) \\ & = \frac{h_{n−1}(k_{n−1}x + k_{n−2}) − k_{n−1}(h_{n−1}x + h_{n−2})}{(k_{n−1}x + k_{n−2})^{2}} \end{aligned}

= \frac{h_{n−1}k_{n−2} − k_{n−1}h_{n−2}}{(k_{n−1}x + k_{n−2})^{2}} = \frac{(−1)^{n}}{(k_{n−1}x + k_{n−2})^{2}} .

Since n ≥ 2 , k_{n−1} > 0 and k_{n−2} > 0 , so k_{n−1}x + k_{n−2} > 0 for all x > 0 ; therefore f_{n} is differentiable on (0, ∞) . In fact, it is monotone there: increasing if n is even, or decreasing if n is odd. (This generalizes Exercise 7.1.5 if n ≥ 2 .)

Therefore f_{n}(ξ_{n}) = ⟨a_{0}, …, a_{n−1}, ξ_{n}⟩ = ξ is between

lim_{x→0^{+}} f_{n}(x) = \frac{h_{n−2}}{k_{n−2}} = r_{n−2}  and  lim_{x→∞} f_{n}(x) = \frac{h_{n−1}}{k_{n−1}} = r_{n−1}

(i.e., r_{n−2} < ξ < r_{n−1} or r_{n−1} < ξ < r_{n−2} ).

In particular, |ξ − r_{n−1}| < |r_{n−1} − r_{n−2}|. Since |r_{n−1} − r_{n−2}| → 0 as n → ∞, we have lim_{n→∞} |ξ − r_{n}| = 0 , so lim_{n→∞} r_{n} = ξ; therefore ξ = θ. □ Corollary. ξ is in the image of the map f defined earlier, so f is surjective. Therefore

f is bijective.

Summarizing, we have bijections:

ℚ = {rational numbers} ↔ {finite simple continued fractions
⟨a_{0}, …, a_{n}⟩ with n = 0 or a_{n} > 1}

↔ {finite simple continued fractions

⟨a_{0}, …, a_{n}⟩ with n > 0 and a_{n} = 1}

and

ℝ \ ℚ = {irrational real numbers} ↔ {infinite simple continued fractions} .

Example Computations

(1) Let ξ = \sqrt{1}0 . Then

a_{0} = [\sqrt{10}] = 3 ; ξ_{1} = \frac{1}{\sqrt{10} − 3} = \frac{\sqrt{10} + 3}{10 − 3^{2}} = \sqrt{10} + 3
a_{1} = [\sqrt{10} + 3] = 6 ; ξ_{2} = \frac{1}{(\sqrt{10} + 3) − 6} = \frac{1}{\sqrt{10} − 3} = \sqrt{10} + 3 = ξ_{1} ;

therefore \sqrt{10} = ⟨3, 6, 6, … ⟩.

(2) Let ξ = \sqrt{6} . Then

a_{0} = [\sqrt{6}] = 2 ; ξ_{1} = \frac{1}{\sqrt{6} − 2} = \frac{\sqrt{6} + 2}{6 − 2^{2}} = \frac{\sqrt{6} + 2}{2}
a_{1} = [\frac{\sqrt{6} + 2}{2}] = 2 ; ξ_{2} = \frac{1}{\frac{\sqrt{6}+2}{2} − 2} = \frac{2}{\sqrt{6} + 2 − 4} = \frac{2}{\sqrt{6} − 2}

= \frac{2(\sqrt{6} + 2)}{6 − 4} = \sqrt{6} + 2

a_{2} = [\sqrt{6} + 2] = 4 ; ξ_{3} = \frac{1}{\sqrt{6} + 2 − 4} = \frac{1}{\sqrt{6} − 2} = ξ_{1} .

(3) In the opposite direction, what is ⟨1, 2, 1, 3, 1, 3, … ⟩? First find ⟨1, 3, 1, 3, … ⟩. Let θ = ⟨1, 3, 1, 3, … ⟩. Then

θ = 1 + \frac{1}{3 + \frac{1}{θ}} = 1 + \frac{θ}{3θ + 1} = \frac{4θ + 1}{3θ + 1} .

Therefore θ(3θ + 1) − (4θ + 1) = 0 ; 3θ^{2} − 3θ − 1 = 0 ; so

θ = \frac{3 ± \sqrt{9 + 12}}{6} = \frac{3 ± \sqrt{21}}{6} .

Since θ > 1 , it can’t be < \frac{1}{2} , so it must be \frac{3+\sqrt{21}}{6} .

Then

⟨1, 2, 1, 3, 1, 3, … ⟩ = 1 + \frac{1}{2 + _{\frac{1}{\frac{3+\sqrt{21}}{6}}}} ,

whatever that is.

(4) Euler showed that

e = ⟨2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, … ⟩ . Why Do We Study Continued Fractions?

Answer: Diophantine approximation. A large partial quotient a_{n} indicates that (the rational number) ⟨a_{0}, …, a_{n−1}⟩ is

very close to the number ⟨a_{0}, a_{1}, … ⟩ or ⟨a_{0}, …, a_{k}⟩ ( k ≥ n).

Example.

\frac{4}{7} = ⟨0, 1, 1, 3⟩
\frac{4}{7} ≈ 0.571 = ⟨0, 1, 1, 3, 47, 3⟩
\frac{4}{7} ≈ 0.572 = ⟨0, 1, 1, 2, 1, 35⟩