Theorem 35: the best rational approximations come from continued fractions

Like Theorem 31, this post is based on a session that I did with some school students. And as I did there, I encourage you to try the activities for yourself (if you haven’t done them before). I think that the students enjoyed the session; I hope that you enjoy the post!

Here’s a strange looking thing (if you haven’t seen anything like it before):

$1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + ...}}}}}$

What can you say about it? Can you compute it? Does it make sense?

That was an infinite thing (that’s what the dots were supposed to indicate). Here are the first few finite chunks of it:

$1$ , $1 + \frac{1}{1}$ , $1 + \frac{1}{1 + \frac{1}{1}}$ , $1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1}}}$ , …

What can you say about them? Any patterns? Can you explain any patterns? Can you predict what the $n$ th one will look like? I recommend also looking at the differences between consecutive terms in the sequence. Can you say anything interesting about them?

So, what can we say?

Let’s look at the infinite thing first. Let’s call it $x$ (a good strategy in mathematics is to give things names, especially if you’re scared of them!). What can we say about $x$ ?

The right-hand side has a very clear structure. In fact, it’s nested: the denominator of the first fraction is $x$ all over again (because the fraction keeps going forever). So we know that $x = 1 + \frac{1}{x}$ .

Ah, but that’s something we can deal with! If we rearrange, we end up with the quadratic equation $x^2 - x - 1 = 0$ , which is a pretty harmless looking object. We must want the positive root, so we find that $x = \frac{1 + \sqrt{5}}{2}$ . You might recognise that as the golden ratio, often written $\varphi$ . We call the expression above the continued fraction for $\varphi$ .

So far, so good. What do we get if we look at the finite pieces from the beginning of this continued fraction? (These finite pieces are called convergents.) I wrote them out as finite continued fractions above; here they are as more conventional fractions:

$\frac{1}{1}$ , $\frac{2}{1}$ , $\frac{3}{2}$ , $\frac{5}{3}$ , $\frac{8}{5}$ , $\frac{13}{8}$ , …

Do you recognise the numbers appearing in the numerators and denominators here? They’re the Fibonacci numbers. Of course, as mathematicians we are interested to see these numbers appearing, but we are not convinced that the convergents are ratios of consecutive Fibonacci numbers unless we can prove this. I’ll leave this as an exercise for you (it shouldn’t be too hard).

What else? Did you look at the differences between consecutive convergents? I think I’ll leave this as an exercise too. See what you can discover (and prove)! (Hint: there is an identity involving Fibonacci numbers that you might find helpful. One of the students with whom I was working last week told me that it’s called Cassini’s identity. So there you go!)

I recommend that you compute the first few decimal places of $\varphi$ , and of the convergents above. If you do so, you’ll see that the convergents seem to converge to $\varphi$ (hence the name!). That is, they get closer and closer. If you look more carefully, you’ll see that they are alternately slightly too large and slightly too small, and they `trap’ $\varphi$ between them. You might like to try to prove all this…

We’ve seen how to write certain rational numbers (namely ratios of consecutive Fibonacci numbers) as finite continued fractions. Is this a special feature of these ratios, or are there other rational numbers that can be written in this form? What numbers can we write in the form

$a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{a_4 + ...}}}}$ ,

for suitable positive integers $a_i$ (allowing $a_0$ to be any integer, if you like)? By the way, the $a_i$ are called the partial quotients. (For example, can you write $\frac{31}{11}$ in this form?) Try this before reading on!

Hopefully you will have discovered that it is possible to write $\frac{31}{11}$ in this form, and indeed that it seems to be possible to write any positive rational number in this form. How can we find the continued fraction representation of $\frac{31}{11}$ ? (By the way, I’ve been a bit sloppy there: I’ve said “the continued fraction representation”, but for all we know there might be more than one! Exercise: think about this.)

If we write $\frac{31}{11}$ as a continued fraction, then the first denominator will be bigger than 1, so the first fraction will be between 0 and 1, so the first integer ( $a_0$ ) must be the integer part of $\frac{31}{11}$ (the bit before the decimal point, if you like). So we want $a_0 = 2$ . Now we can subtract $a_0 = 2$ from $\frac{31}{11}$ and take the reciprocal (“do 1 over it”), and then apply the same process. Doing this repeatedly, we find that

$\frac{31}{11} = 2 + \frac{1}{\frac{11}{9}} = 2 + \frac{1}{1 + \frac{1}{\frac{9}{2}}} = 2 + \frac{1}{1 + \frac{1}{4 + \frac{1}{2}}}$ .

And it seems that we ought to be able to do something similar with any positive rational.

If you stare at it for a bit, you might realise that this process has a lot in common with Euclid’s algorithm, and in fact it really is the same thing in disguise. The proof that Euclid’s algorithm terminates transfers across to show that any positive rational number can be written as a finite continued fraction. (The key in Euclid’s algorithm is that the remainders form a strictly decreasing sequence of non-negative integers, which must terminate; the key here is that the denominators form a strictly decreasing sequence of positive integers, which must terminate.) You might like to play with this a bit more; I think that it’s quite nice!

OK, so positive rational numbers give finite continued fractions, and it doesn’t take very much thought to see that finite continued fractions give rational numbers. But we know that there are other numbers in the world; we saw one earlier ( $\varphi = \frac{1 + \sqrt{5}}{2}$ ). What can we say about them?

I encourage you to try to find the first few partial quotients in the continued fraction representation of $\pi$ (if $\pi$ has such a thing!). For this purpose, I suggest that you pretend that your calculator knows $\pi$ exactly. (It doesn’t, but it’ll do for this!)

Done that? Did you find that

$\pi = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{1 + \frac{1}{292 + ...}}}}$ ?

I suggest that you work out the first few convergents, both as fractions and as decimals, and compare them to $\pi$ . I suggest you also try thinking about the differences between consecutive convergents, and see whether you can find anything interesting. (Remember that you did this exercise for the continued fraction at the start of this post too!)

There are two points I want to make here. One is that the convergents really do converge to $\pi$ . I’ve been rather casual about writing infinite continued fractions without establishing whether it makes sense to do so. It turns out that one can do some careful checking to see that this is all legitimate.

The other is that the convergents to $\pi$ that you found above are really pretty good rational approximations to $\pi$ , aren’t they? And that’s this week’s theorem.

Theorem The best rational approximations come from continued fractions.

Slightly more formally, if $\frac{p_n}{q_n}$ is a convergent for $\theta$ , then the best rational approximation to $\theta$ with denominator at most $q_n$ is $\frac{p_n}{q_n}$ .

For example, the best rational approximation to $\pi$ with denominator less than 113 is 355/113. Have a look at that as a decimal: it’s much closer to $\pi$ than 3.14 (which is the fraction 314/100). A naive approach to finding a rational approximation to $\pi$ would be to truncate the decimal expansion after a suitable number of digits, but that will lead to a much larger denominator than the convergent to $\pi$ that gives the same error. The moral of the story is that you should always use convergents when looking for rational approximations! (This applies to other irrational numbers too, not just $\pi$ : that’s what the theorem tells us.)

I’m not going to prove the theorem here; I think this post is long enough now.

Just before I suggest places to read more about this topic, I’d like to encourage you to compute the continued fraction expansions of $\sqrt{2}$ and $\sqrt{3}$ — without a calculator! (You don’t need it.) There are lots of interesting patterns and things to notice and explain there; I hope that you might find it interesting to explore.

9 Responses to “Theorem 35: the best rational approximations come from continued fractions”

S Says:
January 9, 2011 at 6:15 pm
Though the convergents of the continued fraction are best rational approximations, not *all* best rational approximations are convergents (though they can still be got from the continued fraction). For instance, the sequence of best rational approximations of π is:

3 , 13/4 , 16/5 , 19/6 , 22/7 , 179/57 , 201/64 , 223/71 , 245/78 , 267/85 , 289/92 , 311/99 , 333/106 , 355/113 , …

Note that only a few of them are actual convergents.
theoremoftheweek Says:
January 26, 2011 at 9:17 am
I guess that depends exactly how you’re counting — but I’d still rather look for convergents that come from continued fractions.
S Says:
January 26, 2011 at 6:43 pm
I’m not sure what you meant by counting.

Well, you didn’t define exactly what you meant by “best rational approximation”, but it seemed that you meant:

p/q is a best rational approximation of θ if the nearest rational approximation of θ with denominator at most q is p/q.

Assuming that this is your definition, then it is true that all convergents are best rational approximations, and false that all best rational approximations are convergents. If you meant some other definition of course (which?), then it’s possible that under that definition the convergents are precisely give all best rational approximations. It would be nice to include the definition, in that case.

Just wanted to point out this fact, for completeness. Nice post (and great blog), though!
Number Theory: Lecture 20 « Theorem of the week Says:
November 21, 2011 at 12:10 pm
[…] Theorem 63: Let be a natural number, and let have convergents . If and are integers with , then . (So .) The key idea of the proof was to find a way to link and (about which we know very little) with , , and (about which we know quite a lot). We were able to do this by finding integers and such that and . By thinking about the signs of and (which must be different), we were able to obtain a lower bound for . […]
S Says:
November 29, 2011 at 10:22 am
Returning to this: the convergents are all the best rational approximations if you adopt the (strange but mathematically useful) convention that you’re trying to minimise $|q\theta - p|$ .

It would be great to point out that you’re using this definition (or some definition for which this is true) rather than the more natural (but mathematically messy) definition that a better rational approximation is one for which $\displaystyle |\theta - \frac{p}{q}|$ is smaller.
theoremoftheweek Says:
November 29, 2011 at 10:28 am
Thanks for putting that so clearly — I agree that my vagueness in the post did not spell this out.
Sutton Trust summer school 2012 « Theorem of the week Says:
August 16, 2012 at 11:47 am
[…] arithmetic. In the third and final lecture, we mentioned that is irrational, and talked about continued fractions. There are many proofs that is irrational. We mentioned that there are many more irrational […]
Sutton Trust summer school 2013 | Theorem of the week Says:
August 15, 2013 at 9:11 am
[…] arithmetic. In the third and final lecture, we mentioned that is irrational, and talked about continued fractions. There are many proofs that is irrational. A couple of the problems on the examples sheet are […]
Number Theory: Lecture 20 | Theorem of the week Says:
November 25, 2013 at 11:33 am
[…] Theorem 63: Let be a natural number. If and are integers with , then . So in some sense continued fractions give the best rational approximations. We proved this by writing and for some integers and and arguing from there. […]

Theorem of the week