Value of Simple Continued Fraction

Theorem

Let $\left[{a_1, a_2, a_3, \ldots}\right]$ be a continued fraction expansion.

Let the numerators and denominators $p_1, p_2, p_3, \ldots$ and $q_1, q_2, q_3, \ldots$ be defined as:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p_1\)	\(=\)	\(\displaystyle a_1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle q_1\)	\(=\)	\(\displaystyle 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p_2\)	\(=\)	\(\displaystyle a_1 a_2 + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle q_2\)	\(=\)	\(\displaystyle a_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p_k\)	\(=\)	\(\displaystyle a_k p_{k-1} + p_{k-2}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle q_k\)	\(=\)	\(\displaystyle a_k q_{k-1} + q_{k-2}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Simple Finite Continued Fraction

The value of $\left[{a_1, a_2, a_3, \ldots, a_n}\right]$ is $\displaystyle \frac {p_n} {q_n}$.

Corollary to SFCF

Let $\left[{a_1, a_2, a_3, \ldots}\right]$ be any continued fraction expansion.

Let the numerators $p_1, p_2, p_3, \ldots$ and denominators $q_1, q_2, q_3, \ldots$ be defined as in the main theorem.

Then its convergents are:

$\displaystyle C_k = \frac {p_k} {q_k}$

Simple Infinite Continued Fraction

The value of $\left[{a_1, a_2, a_3, \ldots}\right]$ is the limit of the sequence of convergents $\left \langle {C_n}\right \rangle$.

Corollary to SICF

Let $x$ be the limit of a SICF.

Let $\left \langle {C_n}\right \rangle$ be the sequence of convergents of $x$.

Then $\forall n \ge 1$:

• $C_n < x < C_{n+1}$ or $C_{n+1} < x < C_n$
• $\displaystyle \left|{x - C_n}\right| < \frac 1 {q_n q_{n+1}}$

Proof

Proof for Simple Finite Continued Fraction

Proof by Induction

We will use a proof by induction on the number $n$ of partial quotients in the continued fraction expansion:

For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition $\displaystyle \left[{a_1, a_2, a_3, \ldots, a_n}\right] = \frac {p_n} {q_n}$.

Basis for the Induction

• $P(1)$ is true, as the result holds for any continued fraction expansion $\displaystyle \left[{a_1}\right] = \frac {a_1} 1 = \frac {p_1} {q_1}$.

• $P(2)$ is true, as:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left[{a_1, a_2}\right]\)	\(=\)	\(\displaystyle a_1 + \frac 1 {a_2}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {a_1 a_2 + 1} {a_2}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {p_2} {p_1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

This is our basis for the induction.

Induction Hypothesis

• Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.

So this is our induction hypothesis:

$\displaystyle \left[{a_1, a_2, a_3, \ldots, a_k}\right] = \frac {p_k} {q_k}$

Then we need to show:

$\displaystyle \left[{a_1, a_2, a_3, \ldots, a_k, a_{k+1}}\right] = \frac {p_{k+1}} {q_{k+1}}$

Induction Step

This is our induction step:

Consider $\left[{a_1, a_2, a_3, \ldots, a_k, a_{k+1}}\right]$.

The numerators are $p_1, p_2, p_3, \ldots, p_k, p_{k+1}$ and denominators are $q_1, q_2, q_3, \ldots, q_k, q_{k+1}$.

By the second continued fraction identity, we have:

$\left[{a_1, a_2, a_3, \ldots, a_k, a_{k+1}}\right] = \left[{a_1, a_2, a_3, \ldots, a_{k-1}, a_k'}\right]$

where $\displaystyle a_k' = a_k + \frac 1 {a_{k+1}}$.

Consider the RHS: take the continued fraction expansion $\left[{a_1, a_2, a_3, \ldots, a_{k-1}, a_k'}\right]$.

• Its numerators are $p_1, p_2, p_3, \ldots, p_{k-1}$ and $\displaystyle p_k'$ where $\displaystyle p_k' = \left({a_k + \frac 1 {a_{k+1}}}\right) p_{k-1} + p_{k-2}$ by definition.
• Its denominators are $q_1, q_2, q_3, \ldots, p_{k-1}$ and $q_k'$ where $\displaystyle q_k' = \left({a_k + \frac 1 {a_{k+1}}}\right) q_{k-1} + q_{k-2}$ by definition.

As it has just $k$ partial quotients, the induction hypothesis tells us that its value is $\displaystyle \frac {p_k'} {q_k'}$.

So:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left[{a_1, a_2, a_3, \ldots, a_k, a_{k+1} }\right]\)	\(=\)	\(\displaystyle \frac {p_k'} {q_k'}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {\left({a_k + \frac 1 {a_{k+1} } }\right) p_{k-1} + p_{k-2} } {\left({a_k + \frac 1 {a_{k+1} } }\right) q_{k-1} + q_{k-2} }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {a_{k+1} \left({a_k p_{k-1} + p_{k-2} }\right) + p_{k-1} } {a_{k+1} \left({a_k q_{k-1} + q_{k-2} }\right) + q_{k-1} }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {a_{k+1} p_k + p_{k-1} } {a_{k+1} q_k + q_{k-1} }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {p_{k+1} } {q_{k+1} }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore $\displaystyle \left[{a_1, a_2, a_3, \ldots, a_k, a_{k+1}}\right] = \frac {p_{k+1}} {q_{k+1}}$.

$\blacksquare$

Proof of Corollary

Follows immediately from the definition of convergent of continued fraction and the theorem.

$\blacksquare$

Proof for Simple Infinite Continued Fraction

We need to show that for any SICF its sequence of convergents $\left \langle {C_n}\right \rangle$ always tends to a limit.

Several techniques can be used here, but a quick and easy one is to show that $\left \langle {C_n}\right \rangle$ is a Cauchy sequence.

We have that:

$\displaystyle \left|{C_{k+1} - C_k}\right| = \frac 1 {q_{k+1} q_k}$

by Properties of Convergents of Continued Fractions.

From Denominators of Continued Fraction are Strictly Increasing, we have that for sufficiently large $k$, $q_k > k$.

So:

$\displaystyle \frac 1 {q_{k+1} q_k} < \frac 1 {\left({k+1}\right) k} < \frac 1 {k^2}$

But $\displaystyle \left \langle {\frac 1 {k^2}}\right \rangle$ is a basic null sequence.

So by the Squeeze Theorem $\displaystyle \frac 1 {q_{k+1} q_k} \to 0$ as $k \to \infty$.

So $\left \langle {C_n}\right \rangle$ is indeed a Cauchy sequence.

Hence the result.

$\blacksquare$

Proof of Corollary to SICF

Immediate.

Note that:

$\displaystyle \left|{x - C_n}\right| < \left|{C_{n+1} - C_n}\right| = \frac 1 {q_n q_{n+1}}$

$\blacksquare$