Math 115. Slides from the Lecture of November 19

Infinite Simple Continued Fractions

For today’s class: Let a_{0}, a_{1}, …, be an infinite sequence of integers, with a_{i} > 0 for all i > 0 .

How might we define (the value of) ⟨a_{0}, a_{1}, … ⟩? Answer: As a limit:

⟨a_{0}, a_{1}, … ⟩ = lim_{n→∞}⟨a_{0}, …, a_{n}⟩ .

This leads to looking at functions ⟨a_{0}, …, a_{n−1}, x⟩ with x ∈ ℝ, x > 0 . Note that ⟨a_{0}, x⟩ = a_{0}+ \frac{1}{x} is a decreasing function of x, but ⟨a_{0}, a_{1}, x⟩ = a_{0}+ \frac{1}{a_{1}+ \frac{1}{x}}

is increasing.

We’ll use sequences (h_{n}) and (k_{n}) with n = −2, −1, 0, 1, … defined inductively by

h_{−2} = 0 , h_{−1} = 1 , h_{n} = a_{n}h_{n−1} + h_{n−2} for all n ≥ 0
k_{−2} = 1 , k_{−1} = 0 , k_{n} = a_{n}k_{n−1} + k_{n−2}

Theorem. For any sequence (a_{n}) as above,

⟨a_{0}, …, a_{n−1}, x⟩ = \frac{h_{n−1}x + h_{n−2}}{k_{n−1}x + k_{n−2}} for all n ≥ 0 and all x ∈ ℝ_{>0} .

Proof. Induction on n ∈ ℕ.

Base case: When n = 0 , the left-hand side is ⟨x⟩ = x, and the RHS is

\frac{h_{−1}x + h_{−2}}{k_{−1}x + k_{−2}} = \frac{1x + 0}{0x + 1} = x .

Inductive step: Given n ∈ ℕ, we’ll assume it’s true for n and show it’s true for n + 1 :

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

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

= \frac{h_{n}x + h_{n−1}}{k_{n}x + k_{n−1}} .

□

Proposition. Let n ∈ ℕ and let r_{n} = ⟨a_{0}, …, a_{n}⟩. Then r_{n} = h_{n}/k_{n}. Proof. Let x = a_{n} in the above theorem. Then

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

□

Lemma.

(a). h_{n}k_{n−1} − h_{n−1}k_{n} = (−1)^{n−1} for all n ≥ −1

(b). r_{n} − r_{n−1} = (−1)^{n−1}/k_{n}k_{n−1} for all n ≥ 1 .

Proof. (a). Use induction on n.

Base case: Assume n = −1 . Then

h_{n}k_{n−1} − h_{n−1}k_{n} = (−1)^{n−1} = det [ \begin{matrix}h_{n} & h_{n−1} \\ k_{n} & k_{n−1} \end{matrix} ] = | \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} | = 1 = (−1)^{2} .

Inductive step: If n > 0 and the result is true for n − 1 , then

h_{n}k_{n−1} − h_{n−1}k_{n} = | \begin{matrix}h_{n} & h_{n−1} \\ k_{n} & k_{n−1} \end{matrix} | = det ([ \begin{matrix}h_{n−1} & h_{n−2} \\ k_{n−1} & k_{n−2} \end{matrix} ] [ \begin{matrix}a_{n} & 1 \\ 1 & 0 \end{matrix} ])

= | \begin{matrix}h_{n−1} & h_{n−2} \\ k_{n−1} & k_{n−2} \end{matrix} | · | \begin{matrix}a_{n} & 1 \\ 1 & 0 \end{matrix} | = (−1)^{n−2} · (−1) = (−1)^{n−1} .

(b). For all n ≥ 1 we have

r_{n} − r_{n−1} = \frac{h_{n}}{k_{n}} − \frac{h_{n−1}}{k_{n−1}} = \frac{h_{n}k_{n−1} − h_{n−1}k_{n}}{k_{n}k_{n−1}} = \frac{(−1)^{n−1}}{k_{n}k_{n−1}} .

□

Corollary. gcd(h_{n}, k_{n}) = 1 for all n ≥ 0 . Proof. Indeed, h_{n}k_{n−1} − h_{n−1}k_{n} = ±1 for all n. □

So the fraction r_{n} = h_{n}/k_{n} is in lowest terms for all n.