## 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}
Problem ID: 282 (15 Jul 2006)     Difficulty: 4 Star

Show Problem & Solution