Math 115. Slides from the Lecture of November 17

Finite Simple Continued Fractions

Definition. Let n ∈ ℕ and x_{0}, …, x_{n} ∈ ℝ with x_{i} > 0 for all i > 0 . Then

⟨x_{0}, …, x_{n}⟩ = \{ \begin{matrix}x_{0} & if n = 0 ; \\ x_{0} + \frac{1}{⟨x_{1},...,x_{n}⟩} & if n > 0 . \end{matrix}

Some basic properties:

(1). ⟨x_{0}, x_{1}, …, x_{n}⟩ = x_{0} + \frac{1}{⟨x_{1}, …, x_{n}⟩} if n > 0 (by definition).

(2). ⟨x_{0}, …, x_{n}⟩ = ⟨x_{0}, …, x_{n−2}, x_{n−1} + \frac{1}{x_{n}} ⟩ if n > 0 (by induction)

(3). ⟨x_{0}, …, x_{n}⟩ ≥ x_{0} , with equality ⟺ n = 0 .

Proof of (3). This is proved by induction on n ≥ 0 .

Base case: If n = 0 then it’s easy.

Inductive step: If n > 0 and it’s true for n − 1 , then

⟨x_{1}, …, x_{n}⟩ ≥ x_{1} > 0 ,

so 1/⟨x_{1}, …, x_{n}⟩ > 0 . Therefore

⟨x_{0}, x_{1}, …, x_{n}⟩ = x_{0} + \frac{1}{⟨x_{1}, …, x_{n}⟩} > x_{0} .

□

Definition. A finite continued fraction is simple if x_{0}, …, x_{n} ∈ ℤ.

Every finite simple continued fraction evaluates to a rational number.

We’ll show: Every rational number can be written as a finite simple continued fraction in exactly two ways.

(Later we’ll see: Every (real) irrational number can be written uniquely as an infinite simple continued fraction.)

Theorem (Existence). For all x ∈ ℚ there is a finite sequence a_{0}, …, a_{n} ∈ ℤ with n ∈ ℕ such that a_{i} > 0 for all i > 0 and x = ⟨a_{0}, …, a_{n}⟩.

Proof. …