mathschallenge.net logo

Continued Fraction Recurrence Relation

Problem

Any real number, $\alpha$, can be represented as a continued fraction which may either terminate or be infinite (repeating or non-repeating).

$\alpha = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + ...}}}$

Let $\dfrac{p_n}{q_n}$ be defined as the $n$th convergent:

$\dfrac{p_n}{q_n} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + ... + \cfrac{1}{a_n}}}}$

For example, $\sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + ...}}}$

And the first five convergents are:

$\begin{align}\dfrac{p_0}{q_0} &= 1\\\dfrac{p_1}{q_1} &= \dfrac{3}{2}\\\dfrac{p_2}{q_2} &= \dfrac{7}{5}\\\dfrac{p_3}{q_3} &= \dfrac{17}{12}\\\dfrac{p_4}{q_4} &= \dfrac{41}{29}\\\end{align}$

Prove that the following recurrence relation holds for $n \ge 2$ for all continued fractions:

$$\begin{align}p_n &= a_n p_{n-1} + p_{n-2}\\q_n &= a_n q_{n-1} + q_{n-2}\end{align}$$

Solution

From the definition of a continued fraction, $\dfrac{p_0}{q_0} = a_0 \implies p_0 = a_0$ and $q_0 = 1$.

Similarly $\dfrac{p_1}{q_1} = a_0 + \dfrac{1}{a_1} = \dfrac{a_0 a_1 + 1}{a_1} \implies p_1 = a_0 a_1 + 1$ and $q_1 = a_1$.

In other words, $p_0$, $p_1$, $q_0$, and $q_1$ are clearly defined. Now let us consider the convergent $\dfrac{p_2}{q_2}$ as a continued fraction expansion.

$$\begin{align}\dfrac{p_2}{q_2} &= a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2}}\\&= a_0 + \cfrac{\cfrac{1}{a_1 a_2 + 1}}{a_2}\\&= a_0 + \cfrac{a_2}{a_1 a_2 + 1}\\&= \cfrac{a_0(a_1 a_2 + 1) + a_2}{a_1 a_2 + 1}\\&= \cfrac{a_0 a_1 a_2 + a_0 + a_2}{a_1 a_2 + 1}\\&= \cfrac{a_2(a_0 a_1 + 1) + a_0}{a_1 a_2 + 1}\end{align}$$

But as $p_1 = a_0 a_1 + 1$, $p_0 = a_0$, $q_1 = a_1$, and $q_0 = 1$, we get:

$$\dfrac{p_2}{q_2} = \dfrac{a_2 p_1 + p_0}{a_2 p_1 + q_0}$$

Hence the recurrence relation is true for $n = 2$.

Now suppose that the recurrence relation holds for $n = k$, and consider the continued fraction expansions of the convergents $\dfrac{p_k}{q_k}$ and $\dfrac{p_{k+1}}{q_{k+1}}$.

$$\dfrac{p_k}{q_k} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + ... + \cfrac{1}{a_k}}}}$$$$\dfrac{p_{k+1}}{q_{k+1}} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + ... + \cfrac{1}{a_k + \cfrac{1}{a_{k+1}}}}}}$$

It can be seen that going from $\dfrac{p_k}{q_k}$ and $\dfrac{p_{k+1}}{q_{k+1}}$ we have replaced $a_k$ with $a_k + \dfrac{1}{a_{k+1}}$.

$$\begin{align}\therefore \dfrac{p_k}{p_k} = \dfrac{a_k p_{k-1} + p_{k-2}}{a_k q_{k-1} + q_{k-2}} \rightarrow \dfrac{p_{k+1}}{q_{k+1}} &= \dfrac{\left(a_k + \dfrac{1}{a_{k+1}}\right) p_{k-1} + p_{k-2}}{\left(a_k + \dfrac{1}{a_{k+1}}\right) q_{k-1} + q_{k-2}}\\&= \dfrac{a_{k+1} a_k p_k-1 + p_{k-1} + a_{k+1} p_{k+2}}{a_{k+1} a_k p_{k-1} + q_{k-1} + a_{k+1} q_{k-2}}\\&= \dfrac{a_{k+1}(a_k p_{k-1} + p_{k-2}) + p_{k-1}}{a_{k+1}(a_k q_{k-1} + q_{k-2}) + q_{k-1}}\\&= \dfrac{a_{k+1} p_k + p_{k-1}}{a_{k+1} q_k + q_{k-1}}\end{align}$$

This is the expected outcome for $\dfrac{p_{k+1}}{q_{k+1}}$. As the recurrence relation is true for $n = 2$, and $p_0$, $p_1$, $q_0$, and $q_1$ are properly defined, we have shown that the recurrence relation holds for all values of $n \ge 2$.

However, for practical purposes it is convenient for programmers to set $p_{-1} = 1$, $q_{-1} = 0$, $p_0 = a_0$, and $q_0 = 1$. Then the recurrence relation holds for $n \ge 1$.

Problem ID: 282 (15 Jul 2006)     Difficulty: 4 Star

Only Show Problem