Continued Fractions

A fraction inside a fraction

$\sqrt{2}$√2 is irrational: no fraction with whole numbers on the top and bottom is exactly equal to it. Fractions come close, since ${\left(\frac{7}{5}\right)}^2=\frac{49}{25}=1.96$(7/5)² = 49/25 = 1.96, which is just under 2, but none lands on it.

There is still a way to write $\sqrt{2}$√2 exactly with whole numbers, if the fraction is allowed to go on forever. $\sqrt{2}$√2 is 1 plus 1 over a number; that number is 2 plus 1 over another number; that one is 2 plus 1 over another, and so on without end:

$\sqrt{2}=1+\frac{1}{\left(2+\frac{1}{\left(2+\frac{1}{\left(2+\dots \right)}\right)}\right)}$√2 = 1 + 1/(2 + 1/(2 + 1/(2 + …)))

A fraction built like this, a whole number plus 1 over another whole number plus 1 over another, is called a continued fraction. The fractions stack up like a tower, and each whole number in it is one level of the tower.

The continued fraction for $\sqrt{2}$√2. Each level is a whole number plus 1 over the level below it, and the dots say that the levels never stop.

Why every level is 2

$\sqrt{2}$√2 is 1.414…, so it is 1 plus a part that is less than 1: $\sqrt{2}=1+\left(\sqrt{2}-1\right)$√2 = 1 + (√2 − 1). The part $\sqrt{2}-1$√2 − 1 can be written as 1 over something. Multiply it by $\sqrt{2}+1$√2 + 1, using the difference of two squares: $\left(\sqrt{2}-1\right)\left(\sqrt{2}+1\right)={\left(\sqrt{2}\right)}^2-1^2=2-1=1$(√2 − 1)(√2 + 1) = (√2)² − 1² = 2 − 1 = 1. Two numbers that multiply to 1 are reciprocals, so $\sqrt{2}-1=\frac{1}{\left(\sqrt{2}+1\right)}$√2 − 1 = 1/(√2 + 1), and $\sqrt{2}=1+\frac{1}{\left(1+\sqrt{2}\right)}$√2 = 1 + 1/(1 + √2).

Now look at the $1+\sqrt{2}$1 + √2 at the bottom. It is $2+\left(\sqrt{2}-1\right)$2 + (√2 − 1), and $\sqrt{2}-1$√2 − 1 is $\frac{1}{\left(1+\sqrt{2}\right)}$1/(1 + √2) again, so $1+\sqrt{2}=2+\frac{1}{\left(1+\sqrt{2}\right)}$1 + √2 = 2 + 1/(1 + √2). Substitute that for the bottom: $\sqrt{2}=1+\frac{1}{\left(2+\frac{1}{\left(1+\sqrt{2}\right)}\right)}$√2 = 1 + 1/(2 + 1/(1 + √2)).

The bottom is $1+\sqrt{2}$1 + √2 once more, so the same substitution works again and adds another level with a 2 in it: $\sqrt{2}=1+\frac{1}{\left(2+\frac{1}{\left(2+\frac{1}{\left(1+\sqrt{2}\right)}\right)}\right)}$√2 = 1 + 1/(2 + 1/(2 + 1/(1 + √2))). Every substitution leaves $1+\sqrt{2}$1 + √2 at the bottom, so the substituting never ends, and every level below the top is 2.

The tower cannot stop, either. A tower that stops folds up into an ordinary fraction, as the next section shows, and $\sqrt{2}$√2 is not equal to any fraction.

Below the top, each level is 2 plus 1 over the next level, and the next level is the same again.

Stop the tower and fold it up

Cut the tower off after two levels of 2: $1+\frac{1}{\left(2+\frac{1}{2}\right)}$1 + 1/(2 + 1/2). Now it has a bottom, and it can be worked out as an ordinary fraction.

Work from the bottom up. The bottom level is $2+\frac{1}{2}=\frac{5}{2}$2 + 1/2 = 5/2. The level above is 1 divided by that: $1÷\frac{5}{2}=1\times \frac{2}{5}=\frac{2}{5}$1 ÷ 5/2 = 1 × 2/5 = 2/5, because dividing by a fraction multiplies by its reciprocal. Last, the top: $1+\frac{2}{5}=\frac{7}{5}$1 + 2/5 = 7/5.

So the tower cut off after two levels is $\frac{7}{5}$7/5, which is 1.4. Its square is $\frac{49}{25}=1.96$49/25 = 1.96, close to 2.

The top cannot go first. The top level is 1 plus 1 divided by everything below it, and that is not known until the levels below it have been worked out.

The tower cut off after two levels of 2. With nothing below the last 2, it folds up to $\frac{7}{5}$7/5.

Closer and closer, from both sides

Cut the tower off at each level in turn and you get a list of fractions, called the convergents of the continued fraction. The top level alone is 1. One level of 2 gives $1+\frac{1}{2}=\frac{3}{2}$1 + 1/2 = 3/2. Two levels give $\frac{7}{5}$7/5, as above.

Each convergent gives the next one quickly, by the same step that built the tower: next $=1+\frac{1}{\left(1+\text{this one}\right)}$= 1 + 1/(1 + this one). From $\frac{7}{5}$7/5: $1+\frac{7}{5}=\frac{12}{5}$1 + 7/5 = 12/5, one over that is $\frac{5}{12}$5/12, and $1+\frac{5}{12}=\frac{17}{12}$1 + 5/12 = 17/12. From $\frac{17}{12}$17/12: $1+\frac{17}{12}=\frac{29}{12}$1 + 17/12 = 29/12, one over that is $\frac{12}{29}$12/29, and $1+\frac{12}{29}=\frac{41}{29}$1 + 12/29 = 41/29.

As decimals, $\frac{3}{2}=1.5$3/2 = 1.5, $\frac{7}{5}=1.4$7/5 = 1.4, $\frac{17}{12}=1.4167$17/12 = 1.4167 and $\frac{41}{29}=1.4138$41/29 = 1.4138, to 4 decimal places, while $\sqrt{2}=1.4142$√2 = 1.4142. So 1 is less than $\sqrt{2}$√2, $\frac{3}{2}$3/2 is greater, $\frac{7}{5}$7/5 is less, $\frac{17}{12}$17/12 is greater and $\frac{41}{29}$41/29 is less: the convergents fall on alternate sides of $\sqrt{2}$√2, and each one is nearer than the one before.

Their squares show how near. $3^2=9$3² = 9 and $2\times 2^2=8$2 × 2² = 8; $7^2=49$7² = 49 and $2\times 5^2=50$2 × 5² = 50; $17^2=289$17² = 289 and $2\times 12^2=288$2 × 12² = 288; $41^2=1681$41² = 1681 and $2\times 29^2=1682$2 × 29² = 1682. Each time the top squared is 1 more or 1 less than twice the bottom squared, so ${\left(\frac{17}{12}\right)}^2=\frac{289}{144}$(17/12)² = 289/144 misses 2 by only $\frac{1}{144}$1/144, and ${\left(\frac{41}{29}\right)}^2=\frac{1681}{841}$(41/29)² = 1681/841 misses it by only $\frac{1}{841}$1/841.

$\frac{3}{2}$3/2 is greater than $\sqrt{2}$√2 and $\frac{7}{5}$7/5 is less than it, and $\frac{7}{5}$7/5 is much nearer.

The same line zoomed in 20 times: $\frac{17}{12}$17/12 is greater than $\sqrt{2}$√2, and $\frac{41}{29}$41/29 is less than it and nearer still.

The usual mistakes

Starting at the top. The top of $1+\frac{1}{\left(2+\frac{1}{2}\right)}$1 + 1/(2 + 1/2) is 1 plus 1 over the whole bottom part, so the bottom part, $2+\frac{1}{2}=\frac{5}{2}$2 + 1/2 = 5/2, has to be worked out first.

Folding the wrong number of levels. Count the 2s in the tower: two 2s give $\frac{7}{5}$7/5. Leaving the bottom 2 out gives $\frac{3}{2}$3/2, and folding one 2 too many gives $\frac{17}{12}$17/12.

Forgetting the 1 on top. After $1÷\frac{5}{2}=\frac{2}{5}$1 ÷ 5/2 = 2/5, the top level still adds its 1: the answer is $1+\frac{2}{5}=\frac{7}{5}$1 + 2/5 = 7/5, not $\frac{2}{5}$2/5.

Writing a fraction as a continued fraction

The fold can be run backwards, to turn a fraction into a continued fraction. Take $\frac{7}{5}$7/5. Divide: 7 = 1 × 5 + 2, so $\frac{7}{5}=1+\frac{2}{5}$7/5 = 1 + 2/5. The whole number 1 is the first term.

Now write the fractional part as 1 over something: $\frac{2}{5}=\frac{1}{\left(\frac{5}{2}\right)}$2/5 = 1/(5/2). Divide again: 5 = 2 × 2 + 1, so $\frac{5}{2}=2+\frac{1}{2}$5/2 = 2 + 1/2, and the next term is 2. The last fractional part is $\frac{1}{2}$1/2, which is 1 divided by 2, so the last term is 2 and the division ends. So $\frac{7}{5}=1+\frac{1}{\left(2+\frac{1}{2}\right)}$7/5 = 1 + 1/(2 + 1/2), the tower from before.

The terms are written in a list, with a semicolon after the whole-number part: $\frac{7}{5}=\left[1;2,2\right]$7/5 = [1; 2, 2], and $\sqrt{2}=\left[1;2,2,2,\dots \right]$√2 = [1; 2, 2, 2, …]. For a fraction the list always ends, because each remainder is smaller than the number divided by, and whole numbers cannot get smaller forever. For $\sqrt{2}$√2 the list never ends.