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):
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:
, , , , …
What can you say about them? Any patterns? Can you explain any patterns? Can you predict what the 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 (a good strategy in mathematics is to give things names, especially if you’re scared of them!). What can we say about ?
The right-hand side has a very clear structure. In fact, it’s nested: the denominator of the first fraction is all over again (because the fraction keeps going forever). So we know that .
Ah, but that’s something we can deal with! If we rearrange, we end up with the quadratic equation , which is a pretty harmless looking object. We must want the positive root, so we find that . You might recognise that as the golden ratio, often written . We call the expression above the continued fraction for .
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:
, , , , , , …
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 , and of the convergents above. If you do so, you’ll see that the convergents seem to converge to (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’ 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
for suitable positive integers (allowing to be any integer, if you like)? By the way, the are called the partial quotients. (For example, can you write in this form?) Try this before reading on!
Hopefully you will have discovered that it is possible to write 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 ? (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 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 () must be the integer part of (the bit before the decimal point, if you like). So we want . Now we can subtract from and take the reciprocal (“do 1 over it”), and then apply the same process. Doing this repeatedly, we find that
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 (). What can we say about them?
I encourage you to try to find the first few partial quotients in the continued fraction representation of (if has such a thing!). For this purpose, I suggest that you pretend that your calculator knows exactly. (It doesn’t, but it’ll do for this!)
Done that? Did you find that
I suggest that you work out the first few convergents, both as fractions and as decimals, and compare them to . 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 . 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 that you found above are really pretty good rational approximations to , aren’t they? And that’s this week’s theorem.
Theorem The best rational approximations come from continued fractions.
Slightly more formally, if is a convergent for , then the best rational approximation to with denominator at most is .
For example, the best rational approximation to with denominator less than 113 is 355/113. Have a look at that as a decimal: it’s much closer to than 3.14 (which is the fraction 314/100). A naive approach to finding a rational approximation to 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 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 : 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 and — 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.
As usual, I’ll recommend Davenport‘s The Higher Arithmetic. (I’m sure I’ve not previously read the biography to which I linked there — I’m not sure how that is possible, given how often I’ve mentioned Davenport! I must have neglected to find a biography previously; my apologies.) There’s also a section about continued fractions (including this post’s theorem) in Baker‘s A concise introduction to the theory of numbers, and of course Wikipedia has something to say on the subject. This business of finding rational approximations is called Diophantine approximation; there are many books on this subject (for example by Cassels, by Schmidt, and by R.C. Baker, to give three examples off the top of my head). The theory of Diophantine approximation goes much further than this post; it’s interesting stuff.