I am familiar with the algorithm to calculate the continued fraction of an irrational number, but I was wondering how we can be sure that the fraction actually converges to the irrational we are concerned with. I know how to show the convergence of particular continued fractions, but I don't see how we could do this with a general fraction. I've seen that any finite continued fraction of an irrational is just a matter of algebra, but how can we be sure that repeatedly applying that algorithm gives us something that converges to the relevant irrational? If it helps in answering the question, I am interested in particular in the convergence of continued fractions of surds $\sqrt{n}$, but I thought I should ask for the general case. If it's considerably easer to show convergence for surds then it may be worth separating the cases.
-
2$\begingroup$ proofwiki.org/wiki/… $\endgroup$– PremNov 15, 2022 at 12:17
-
$\begingroup$ This may be helpful suppose $x_n = \frac{p_n}{q_n} \in Q_n$ where $\frac{p_n}{q_n}$ is in reduced form and $x_n \to a, a \notin \mathbb{Q}$ prove $q_n \to \infty$ $\endgroup$– MittensNov 15, 2022 at 16:07
1 Answer
You'll find proofs of the convergence in any decent exposition of continued fractions (Chapter X of Hardy and Wright's An Introduction to the Theory of Numbers, for example).
In particular, if $\ \left\{\frac{p_n}{q_n}\right\}_{n=0}^\infty\ $ are the convergents of the continued fraction expansion of any real number $\ x\ $, where $\ p_n,q_n\ $ are relatively prime integers for each $\ n\ $, and $\ p,q\ $ are any integers with $\ 1\le q\le q_n\ $, then $$ \left|x-\frac{p_n}{q_n}\right|\le\left|x-\frac{p}{q}\right|\ . $$ That is, of all rational approximations to $\ x\ $ with denominators not exceeding $\ q_n\ $ in magnitude,$\ \frac{p_n}{q_n}\ $ is the best. This is Theorem $181$ on p.$151$ of Hardy and Wright's above-cited text, for example. Since it follows from the recursion $\ q_n=$$\,a_nq_{n-1}+$$\,q_{n-2}\ $ (with $\ a_0,a_1,\dots\ $ being the partial quotients) that $\ q_n\rightarrow\infty\ $, then it obviously follows from this theorem, and the density of the rationals in the reals, that $\ \frac{p_n}{q_n}\ $ must converge to $\ x\ $ as $\ n\rightarrow\infty\ $.
-
$\begingroup$ So if I'm getting this right, you're saying that since the nth convergent is always the best approximation with a denominator smaller than $q_n$, and $q_n \rightarrow \infty$, we can be sure that whatever the fraction converges to better approximates $x$ than any rational, and so must be $x$ (because there are rationals between any other number and $x$)? $\endgroup$ Nov 15, 2022 at 17:28
-
$\begingroup$ Yes, that's the argument, although the fact that $\ \frac{p_n}{q_n}\ $ converges to $\ x\ $ would typically be proved well before the theorem about $\ \frac{p_n}{q_n}\ $ being the best of the rational approximations to $\ x\ $ with denominators not exceeding $\ q_n\ $ in magnitude. One of the results given by Theorem $164$ in Hardy and Wright's book, for instance, is that $\ \left|x-\frac{p_n}{q_n}\right|\le\frac{1}{q_nq_{n+1}}\ $, from which the convergence to $\ x\ $ also follows. $\endgroup$ Nov 18, 2022 at 8:16