# Value of Finite Continued Fraction equals Numerator Divided by Denominator

## Theorem

Let $F$ be a field.

Let $\tuple {a_0, a_1, \ldots, a_n}$ be a finite continued fraction of length $n \ge 0$.

Let $p_n$ and $q_n$ be its $n$th numerator and denominator.

Then the value $\sqbrk {a_0, a_1, \ldots, a_n}$ equals $\dfrac {p_n} {q_n}$.

## Proof

We will use a proof by induction on the length $n$.

For all $n \in \Z_{>0}$, let $\map P n$ be the proposition:

$\sqbrk {a_0, a_1, \ldots, a_n} = \dfrac {p_n} {q_n}$

### Basis for the Induction

$\map P 0$ is the case:

$\sqbrk {a_0} = \dfrac {a_0} 1 = \dfrac {p_0} {q_0}$

This holds for any continued fraction.

$\map P 1$ is the case:

 $\ds \sqbrk {a_0, a_1}$ $=$ $\ds a_0 + \frac 1 {a_1}$ $\ds$ $=$ $\ds \frac {a_0 a_1 + 1} {a_1}$ $\ds$ $=$ $\ds \frac {p_1} {q_1}$

This is our basis for the induction.

### Induction Hypothesis

Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.

So this is our induction hypothesis:

$\sqbrk {a_0, a_1, \ldots, a_k} = \dfrac {p_k} {q_k}$

Then we need to show:

$\sqbrk {a_0, a_1, \ldots, a_k, a_{k + 1} } = \dfrac {p_{k + 1} } {q_{k + 1} }$

### Induction Step

This is our induction step:

Consider the continued fraction:

$\sqbrk {a_0, a_1, \ldots, a_k, a_{k + 1} }$

The numerators are:

$p_0, p_1, \ldots, p_k, p_{k + 1}$

and the denominators are:

$q_0, q_1, \ldots, q_k, q_{k + 1}$

By definition of value of a finite continued fraction:

$\sqbrk {a_0, a_1, \ldots, a_k, a_{k + 1} } = \sqbrk {a_0, a_1, \ldots, a_{k - 1}, a_k'}$

where $a_k' = a_k + \dfrac 1 {a_{k + 1} }$

Consider the right hand side.

Take the continued fraction:

$\sqbrk {a_0, a_1, \ldots, a_{k - 1}, a_k'}$

Its numerators are:

$p_0, p_1, \ldots, p_{k-1}$ and $p_k'$

where $p_k' = \paren {a_k + \dfrac 1 {a_{k + 1} } } p_{k - 1} + p_{k - 2}$ by definition.

Its denominators are:

$q_0, q_1, \ldots, p_{k - 1}$ and $q_k'$

where $q_k' = \paren {a_k + \dfrac 1 {a_{k + 1} } } q_{k - 1} + q_{k - 2}$ by definition.

As it has just $k$ partial quotients, the induction hypothesis tells us that its value is:

$\dfrac {p_k'} {q_k'}$

So:

 $\ds \sqbrk {a_0, a_1, \ldots, a_k, a_{k + 1} }$ $=$ $\ds \frac {p_k'} {q_k'}$ $\ds$ $=$ $\ds \frac {\paren {a_k + \frac 1 {a_{k + 1} } } p_{k - 1} + p_{k - 2} } {\paren {a_k + \frac 1 {a_{k + 1} } } q_{k - 1} + q_{k - 2} }$ $\ds$ $=$ $\ds \frac {a_{k + 1} \paren {a_k p_{k - 1} + p_{k - 2} } + p_{k - 1} } {a_{k + 1} \paren {a_k q_{k - 1} + q_{k - 2} } + q_{k - 1} }$ $\ds$ $=$ $\ds \frac {a_{k + 1} p_k + p_{k - 1} } {a_{k + 1} q_k + q_{k - 1} }$ $\ds$ $=$ $\ds \frac {p_{k + 1} } {q_{k + 1} }$

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

Therefore:

$\sqbrk {a_0, a_1, \ldots, a_k, a_{k + 1} } = \dfrac {p_{k + 1} } {q_{k + 1} }$

$\blacksquare$