Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
$a_i<a_i+\frac{1}{a_{i+1}}$ for $a_{i+1}\in\mathbb{N}$ (per definition). As we (kind of) increased $a_i$ to $a_i+\frac{1}{a_{i+1}}=:a_i'$ in the $(i+1)$'st step, we effectively decreased the term $a_{i-1}+\frac{1}{a_i'}$ which effectively increased the term $a_{i-2}+\frac{1}{a_{i-1}+\frac{1}{a_i'}}$ and so on. As all changes must have a finite absolute value >0, the approximants must alternate to below and above the true value. If you must have it with induction, I cannot help you though. –  example Apr 13 '12 at 14:05

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
@Josué: I don't have this result in my paper on Continued Fractions, which I have been working on for 35 years. I should find a place for this. Note that the indices of the convergents in my paper are off by $1$ from yours. –  robjohn Apr 13 '12 at 18:48
    
@Josué: actually, Lemma 5.1 pretty much covers this result, but that proof uses more of the background from earlier in the paper. This proof is more self-contained. –  robjohn Apr 13 '12 at 18:58

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

share|improve this answer
    
Doesn't this only prove, that the arguments alternatingly increase and decrease the approximant? It does not prove, that all decreased ones must actually be less than the final result. Like the sequence $1,2,1.5,2,1.2$ increases and decreases in the shown fashion, but $1.5>1.2$. That this cannot happen is due to $a_i\in\mathbb{N}$. A fact that I miss in you proof. –  example Apr 13 '12 at 14:29
    
@example: I was not finished... :-) –  Did Apr 13 '12 at 14:40
    
i see ^^ Still think you need to expand on the "Since $a_i<a_i'$" part. It is a consequence of the aforementioned $a_{i+1}\in\mathbb{N}$ which I cannot see in your proof. –  example Apr 13 '12 at 14:45
    
No, hold on a sec... That part is correct as it is, but there must be a hole somewhere, as I can find a series that does not show this behaviour as long as $a_i$ must not be a natural number. You never use this requirement... –  example Apr 13 '12 at 14:48
    
Ok, forget what I said. Must have made a mistake in my head. Everything seems to fit =) –  example Apr 13 '12 at 14:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.