mathschallenge.net

Problem

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

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

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}$

Assuming 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}$$

Prove that $\dfrac{p_n}{q_n}$ is irreducible.

---

Solution

Let us consider the difference between two consecutive convergents:

$${p_{k+1} \over q_{k+1}} - {p_k \over q_k} = {p_{k+1} q_k - p_k q_{k+1} \over q_k q_{k+1}} = {D_k \over q_k q_{k+1}}$$

Multiplying through by $q_k q_{k+1}$:

$$\begin{align}D_k &= p_{k+1} q_k - p_k q_{k+1}\\&= (a_{k+1} p_k + p_{k-1}) q_k - p_k (a_{k+1} q_k +q_{k-1})\\&= a_{k+1} p_k q_k + p_{k-1} q_k - a_{k+1} p_k q_k - p_k q_{k-1}\\&= p_{k-1} q_k - p_k q_{k-1}\\&= -(p_k q_{k-1} - p_{k-1} q_k)\\&= -D_{k-1}\end{align}$$

$\therefore D_k = -D_{k-1} = D_{k-2} = ... = (-1)^k D_0$.

But $D_0 = p_1 q_0 - p_0 q_1$, and from the definition of the continued fraction, $\dfrac{p_0}{q_0} = a_0 \implies p_0 = a_0$ and $q_0 = 1$ (as $p_k$ and $q_k$ are integer).

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$.

$\therefore D_0 = (a_1 a_0 + 1) \times 1 - a_0 a_1 = 1.

Hence $D_k = (-1)^k$.

Let $j$ be the highest common factor of $p_n$ and $q_n$; that is, $p_n = j p_n'$ and $q_n = j q_n'$.

$$\begin{align}\therefore D_k &= p_{k+1} q_k - p_k q_{k+1}\\&= p_{k+1} j q_{k+1}' - j p_k' q_{k+1}\\&= j(p_{k+1} q_k' - p_k' q_{k+1})\end{align}$$

But as $D_k = (-1)^k$ we get, $(-1)^k = j(p_{k+1} q_k' - p_k' q_{k+1})$.

Clearly the left hand side is only divisible by 1, and so we conclude that the highest common factor, $j = 1$. Hence $\dfrac{p_n}{q_n}$ is irreducible.

By considerig $\dfrac{p_{k+1}}{q_{k+1}} - \dfrac{p_k}{q_k}$ prove that $\dfrac{p_n}{q_n}$ converges as $n$ increases.