Value of Finite Continued Fraction equals Numerator Divided by Denominator

From ProofWiki
Jump to navigation Jump to search

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 denominators, 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$

Retrieved from "https://proofwiki.org/w/index.php?title=Value_of_Finite_Continued_Fraction_equals_Numerator_Divided_by_Denominator&oldid=670426"