Trouble understanding Khinchin's proof of the recursion formulae $p_k=a_kp_{k-1}+p_{k-2};q_k=a_kq_{k-1}+q_{k-2}$ for continued fractions

60 Views Asked by At

I am trying to understand a particular conundrum that has been bothering me in Khincin's proof of his Theorem 1 in his book Continued Fractions. My precise question is at the end of this post marked with (Question).

Khinchin's Theorem 1 establishes that

$$\begin{cases}p_k=a_kp_{k-1}+p_{k-2}\\\ q_k=a_kq_{k-1}+q_{k-2}\end{cases}$$

for all $k\geq 2$ when

$$\frac{p_k}{q_k} = x = [a_0;a_1,\dots,a_k] = a_0 + \frac{1}{a_1 + \frac{1}{\ddots + \frac{1}{a_n}}}$$

for positive integers $a_i$ with $a_n \geq 2$. Khinchin's proof takes it for granted that if you simplify the continued fraction $ [a_0;a_1,\dots,a_k]$ by expanding summands and flipping ratios (meaning $\frac{1}{\frac{p}{q}} = \frac{q}{p}$), then in the end you get $x = \frac{Q(a_0,\dots,a_k)}{P(a_0,\dots,a_k)}$ for some integers $Q(a_0,\dots,a_k), P(a_0,\dots,a_k)$ such that $\mathrm{gcd}(Q(a_0,\dots,a_k), P(a_0,\dots,a_k)) = 1$. This isn't too hard to prove with induction starting from the fact that $a_n\geq 2$ and considering $a_{n-1} + \frac{1}{a_n}$.

Furthermore Khinchin uses the following equations:

If $[a_0;a_1,\dots,a_n] = \frac{p}{q}$ and $r_1 = [a_1;a_2,\dots,a_n] = \frac{p'}{q'}$, then

$$\begin{cases}p = a_0p' + q'\\\ q = q'\end{cases}$$

since $a_0 + \frac{1}{r_1} = \frac{a_0p + q}{p}$.

The given proof is as follows:

In the case of $k = 2$, the formulas ([the recursion formulas]) are easily verified directly. Let us suppose that they are true for all $k < n$. Let us then consider the continued fraction $[a_1;a_2,\dots,a_n]$, and let us denote by $\frac{p'_r}{q'_r}$ its $r$th-order convergent ([meaning that $\frac{p'_r}{q'_r} = [a_1;a_2,\dots,a_r]]$). Then

$$\begin{cases}p_n = a_0p'_{n-1} + q'_{n-1}\\\ q_n = p'_{n-1}\end{cases}$$

and by hypothesis

$$\begin{cases}p_{n-1}' = a_{n}p'_{n-2} + p'_{n-3} \\\ q_{n-1}' = a_nq'_{n-2} + q'_{n-3}\end{cases}$$

where $a_n$ is in place of $a_{n-1}$ as $[a_1;a_2,\dots,a_n]$ begins with $a_1$ and not $a_0$.

(Question:) What is unclear to me is that if $q_{n} = p'_{n-1}$ then isn't it similarly true that $q_{n-1}' = p_{n-2}'$. But then $p_n = a_np_{n-1} + p_{n-2} = a_0p_{n-1} + p_{n-2}$ which would imply that all $a_n$s, $n\in\mathbb{N}_0$ are equal, which is contradictory in the general case.