Stuck at showing recursion property $q_n=c_nq_{n-1}+q_{n-2}$ of the continuants $q_n$ of $x$'s continued fraction expression $x=\frac{p_n}{q_n}$.

26 Views Asked by At

(Setting:) Take it as granted that every real number can be expressed as a continued fraction $x = [c_0;c_1, c_2,\dots]$ for $c_0;c_1,c_2,\dots \in \mathbb{Z}$ with $x = c_0 + \frac{1}{c_1 + \frac{1}{c_2 + \frac{1}{\ddots}}}$. For the purposes of this post, let us focus on the set $S := [0,1]\setminus\mathbb{Q}$ so that a.) $c_0 = 0$, b.) we do not have to consider signs, c.) we will not run out of the integers $c_n$. A reference I am reading defines the convergent of $x \in S$ as $\frac{p_n(x)}{q_n(x)} = [c_1,\dots,c_n]$, where we have taken the $n$ first natural numbers of $x$'s continued fraction expansion. So here by definition $p_n(x), q_n(x)\in\mathbb{N}$ and $\mathrm{gcd}(p_n(x), q_n(x)) = 1$. The denominator $q_n(x)$ is called the continuant of $x$. The reference later remarks that continuants and convergents have certain nice recursive properties such as if $x = [c_1,c_2,\dots]$, then

1.) $$q_n(x) = c_nq_{n-1}(x) + q_{n-2}(x)$$

and

2.) $$q_n(x)p_{n-1}(x) - q_{n-1}(x)p_n(x) = (-1)^n$$

Unfortunately, the reference does not prove any of these properties and leaves it to the reader.

(Question:) I figured that a the property 1.) could be proved with straightforward induction where I would have to do some manipulation of the continued fraction expression. For $n = 3$, we have

$$[c_1, c_2, c_3] = \frac{1}{c_1 + \frac{1}{c_2 + \frac{1}{c_3}}} = \frac{1 + c_2c_3}{c_1(1 + c_2c_3) + c_3}$$

and at this point I would like to be able to say that $q_3(x) = c_1(1 + c_2c_3) + c_3$. But, the definition of the convergent requires that $\mathrm{gcd}(p_3(x), q_3(x)) = 1$. And I am a bit too rusty with number theory to conclude why $\mathrm{gcd}(1 + c_2c_3, c_1(1 + c_2c_3) + c_3) = 1$.

So is it somehow obvious why the denominator you get after simplifying the $n$th continued fraction $[c_1,\dots,c_n]$ is always in the form $\frac{p_n(x)}{q_n(x)}$ for some two coprime natural numbers $p_n(x), q_n(x)$?