# Continued Fractions

• A finite continued fraction is an expression of the form

• Finite continued fractions with integer terms represent rational numbers.
• Every rational number can be expressed as a finite continued fraction using the Euclidean Algorithm, but the expression is not unique.
• The convergent of is (the value of) the continued fraction .
• The convergents oscillate about the value of the continued fraction.
• The convergents of a continued fraction may be computed from the continued fraction using a recursive algorithm. The algorithm produces rational numbers in lowest terms.

Definition. Let , ... be real numbers, with , ..., positive. A finite continued fraction is an expression of the form

To make the writing easier, I'll denote the continued fraction above by . In most cases, the 's will be integers.

Example.

In short form, .

A little bit of thought should convince you that you can express any rational number as a finite continued fraction in this way. In fact, the expansion corresponds to the steps in the Euclidean algorithm. First,

Rewrite these equations as

You can get the continued fraction I found above by substituting the third equation into the second, and then substituting the result into the first.

Since this is just the Euclidean algorithm, I can use the first two columns of the Extended Euclidean Algorithm table to get the numbers in the continued fraction expansion:

Notice that the successive quotients 2, 1, 3, and 4 are the numbers in the continued fraction expansion.

Example. Find the finite continued fraction expansion for .

Lemma. Every finite continued fraction with integer terms represents a rational number.

Proof. If , then is rational.

Inductively, suppose that a finite continued fraction with "levels" is a rational number. I want to show that

is rational.

By induction,

is rational.

So

is the sum of two rational numbers, which is rational as well.

Example. The continued fraction expansion of a rational number is not unique. For example,

And in general,

I want to talk about infinite continued fractions --- things that look like

In preparation for this, I'll look at the effect of truncating a continued fraction.

Definition. The convergent of the continued fraction is

Note that for , .

Example.

And as well.

The next result gives an algorithm for computing the convergents of a continued fraction. It's important for theoretical reasons, too --- I'll need it for several of the proofs that follow. For the theorem, I won't assume that the 's are integers, since I will need the general result later on.

Theorem. Let , , ..., be positive real numbers. Let

Then the k-th convergent of is .

Proof. First, note that

by regarding the last two terms as a single term.

Note also that , ..., and , ..., are the same for these two fractions, since they only differ in the k-th term.

Now I'll start the proof --- it will go by induction on k. For ,

And for ,

Suppose , and assume that result holds through the k-th convergent. Then

Now this is the k-th convergent of a continued fraction, so by induction this is , where and refer to (as opposed to ). But what are the and for this fraction? They're given inductively by

Now , , , are the same for and , as I noted at the start. On the other hand, the k-th term of is . So

(The next to the last equality also follows by induction.) This shows that the result holds for , so the induction step is complete.

Example.

There is a pattern to the computation of the p's and q's which makes things pretty easy. To get the next p, for instance, multiply the current a by the last p and add the next-to-the-last p.

Notice that the convergents oscillate, and that the fractions which give the convergents are always in lowest terms.

Example.

Again, notice that the convergents oscillate, and that the fractions for the convergents are always in lowest terms.

I'll prove that the convergent fractions are in lowest terms first.

Theorem. Let , , ..., be positive real numbers. Let

Then

Corollary. Let , , ..., be positive integers. Let

For , is in lowest terms.

Proof. implies that .

Proof of the Theorem. I'll induct on k. For ,

Take , and assume the result holds for k. Then

This proves the result for , so the general result is true by induction.

Example. I'll show later that (the golden ratio) has the infinite continued fraction expansion . Here are the first ten convergents:

In fact, . In this case, you can see formally that should be . Let

The roots are . Since the fraction is positive, take the positive root to obtain .

Contact information