All Even-Numbered Convergents of a Finite Continued Fraction Are Less Than the Value

Question

Let $x=[a_0;a_1,a_2]$ be shorthand notation for the continued fraction $$x=a_0+\frac{1}{a_1+\frac{1}{a_2}}.$$ Then every $x\in\mathbb{Q}$ can be represented as a finite continued fraction $[a_0;a_1,a_2,\dots,a_n]$, where $a_0\in\mathbb{Z}$ and $a_1,a_2,\dots,a_n\in\mathbb{N}$. Moreover, let $$\begin{matrix} p_0=a_0 & q_0=1\\ p_1=a_0a_1+1 & q_1=a_1\\ p_k=a_kp_{k-1}+p_{k-2} & q_k=a_kq_{k-1}+q_{k-2} \end{matrix}$$ and define $$C_k=\frac{p_k}{q_k}$$to be the $k$th convergent of $x$.

I am trying to show that for any finite continued fraction, all even-numbered convergents are less than the fraction's value.

For example, let $x=43/30$. Then $$x=1+\frac{1}{2+\frac{1}{3+\frac{1}{4}}},$$ or $x=[1;2,3,4]$. It follows that $C_0=1$, $C_1=3/2$, $C_2=10/7$, and $C_3=43/30$, and both $C_0$ and $C_2$ are less than $x$, as stated.

How can I prove this by induction?

Answer 1

Given that $$ \begin{array}{c} p_0=a_0&\text{and}&q_0=1\\ p_1=a_0a_1+1&\text{and}&q_1=a_1\\ p_k=a_kp_{k-1}+p_{k-2}&\text{and}&q_k=a_kq_{k-1}+q_{k-2}\tag{1} \end{array} $$ notice that $$ p_1q_0-p_0q_1=1\tag{2} $$ and $$ \begin{align} p_{k+1}q_k-p_kq_{k+1} &=(a_kp_k+p_{k-1})q_k-p_k(a_kq_k+q_{k-1})\\ &=-(p_kq_{k-1}-p_{k-1}q_k)\tag{3} \end{align} $$ Equations $(2)$ and $(3)$ show that $$ p_{k+1}q_k-p_kq_{k+1}=(-1)^k\tag{4} $$ Thus, $$ \frac{p_{k+1}}{q_{k+1}}-\frac{p_k}{q_k}=\frac{(-1)^k}{q_kq_{k+1}}\text{ and }\frac{p_k}{q_k}-\frac{p_{k-1}}{q_{k-1}}=\frac{(-1)^{k-1}}{q_{k-1}q_k}\tag{5} $$ adding these equations yields $$ \frac{p_{k+1}}{q_{k+1}}-\frac{p_{k-1}}{q_{k-1}}=(-1)^{k-1}\frac{q_{k+1}-q_{k-1}}{q_{k-1}q_kq_{k+1}}\tag{6} $$ Since $\{q_k\}$ is an increasing sequence, $(6)$ is positive for odd $k$ (even convergents) and negative for even $k$ (odd convergents).

Therefore, $\left\{\dfrac{p_{2k}}{q_{2k}}\right\}$ is increasing and $\left\{\dfrac{p_{2k+1}}{q_{2k+1}}\right\}$ is decreasing.

Answer 2

Write $x=[a_0;a_1,a_2,\ldots]$ as $x=F(a_0,a_1,a_2,\ldots)$, and let us first prove an auxiliary result;

The function $(a_k)_{k\geqslant0}\mapsto F((a_k)_{k\geqslant0})$ is increasing with respect to its even-numbered arguments $a_{2k}$ and decreasing with respect to its odd-numbered arguments $a_{2k+1}$.

Note that $F((a_k)_{k\geqslant0})$ is increasing with respect to $a_0$. Next, assume the sense of variation of $F$ with respect to its $i$th argument is known, namely that $F((a_k)_{k\geqslant0})$ is in/de-creasing with respect to $a_i$. Then $F((b_k)_{k\geqslant0})$ is in/de-creasing with respect to $b_i$, hence $1/F((b_k)_{k\geqslant0})$ is de/in-creasing with respect to $b_i$, which proves that $F((a_k)_{k\geqslant0})=a_0+1/F((b_k)_{k\geqslant0})$ for $b_k=a_{k+1}$ for every $k\geqslant0$, is de/in-creasing with respect to $b_i=a_{i+1}$. Thus a recursion over $i\geqslant0$ yields the result claimed above.

Let us now use this to answer the question asked. Every convergent of $x$ is some $x^{(i)}=[a_0;a_1,a_2,\ldots,a_{i}]$ and $x=[a_0;a_1,a_2,\ldots,a'_{i}]$ where $a'_{i}=[a_i;a_{i+1},a_{i+2},\ldots]$. Since $a_i\lt a'_i$ and every other argument in $x$ and $x^{(i)}$ coincide, the auxiliary result above yields $x^{(i)}\lt x$ for every even $i$ and $x^{(i)}\gt x$ for every odd $i$.

Finally the two crucial facts are that $F((a_k)_{k\geqslant0})$ is (i) increasing with respect to $a_0$ and (ii) a decreasing function of $F((b_k)_{k\geqslant0})$, where $(b_k)_{k\geqslant0}$ is an increasing function of $(a_k)_{k\geqslant1}$.