**Continued Fractions**

**Introduction**

Consider

Euclid's Algorithm, a method for finding the

gcd of two numbers,

e.g. 355 and 113:

355 = 3 * 113 + 16

113 = 7 * 16 + 1

Note we can

rearrange this to get:

355 16 1
----- = 3 + ----- = 3 + -----
113 113 113
------
16
1
= 3 + ------------
1
7 + ----
16

The above is then called the

simple continued fraction representation for the

rational number 355/113. In common mathematical notation, it is written:

355 1 1
----- = 3 + ---- ----
113 7+ 16

or, more easily,

355 / 113 = [3;7,16].
**Cool! So what?**
That's all fine and

dandy, but continued fractions don't start getting really

cool until we consider the simple continued fraction representations for an arbitrary

irrational number α. Letting ⌊

*x*⌋ denote the

floor function (i.e. the greatest integer less than any real number

*x*), we form a

sequence, using a process somewhat analagous to Euclid's Algorithm above:

α_{0} = α and a_{0} = ⌊α⌋

α_{1} = 1 / (α_{0} - a_{0}) and a_{1} = ⌊α_{1}⌋

...

α_{n} = 1 / (α_{n - 1} - a_{n - 1}) and a_{n} = ⌊α_{n}⌋

Then, using the notion developed for finite

SCFs,

α = lim_{n→∞} [a_{0}; a_{1}, ..., a_{n}] = [a_{0}; a_{1}, a_{2}, ...]
The

partial quotients [a

_{0}; a

_{1}, ..., a

_{k}] thus form a

sequence, commonly denoted

*p*_{k}/

*q*_{k}, and known as the sequence of

convergents for α.

**Example**
Let α = √2. Then:

a

_{0} = ⌊√2⌋ = 1

a

_{1} = ⌊ 1 / (√2 - 1) ⌋ = 2

...and it turns out (you can do the math yourself) that

√2 = [1; 2, 2, 2, ...]
This is somewhat

interesting. Note also that:

(√2 - 1)(√2 + 1) = 1, so

√2 = 1 + 1/(1 + √2)... so we can substitute:

√2 = 1 + 1/(1 + 1 + 1/(1 + √2), and continuing, √2 =

1 1 1 1
1 + --- --- --- ---
2+ 2+ 2+ 2+ ...

i.e. this gets us the continued fraction for √2 in a totally different way, without all those nasty ⌊α_{i}⌋!

In fact, it turns out that

any irrational root of a quadratic equation has a simple continued fraction representation that eventually repeats!

This theorem is not so very difficult to prove, but I shall leave the interested reader to investigate for him- or herself. However, a little more background information might help, so see the section below on convergents.

The example given demonstrates a method for finding the value α of a repeating continued fraction [a_{0}; a_{1}, ..., a_{k}] with a repeating part of length *h* (which might start after some initial constants). Basically, you multiply to subtract off the beginning bits, then call the repeating part *x* and plug it in. This will yield a quadratic equation in *x*, which can then be solved any way one wishes. The process is somewhat tedious, and so I shall not give an example here.

**The Golden Number, φ**

One interesting quadratic irrationality of note is the golden number, φ. As you may or may not know, φ is the positive root of

*x*^{2} + *x* - 1 = 0

so by the quadratic formular,

φ = (-1 + √5)/2.

So we can plug φ in for *x* and rearrange:

φ^{2} + φ = 1 ⇒ φ = 1 / (1 + φ)

So using what should now be a familiar strategy of substitution, φ =

1 1
1 + --- --- ...
1+ 1+

i.e. φ = [1;1, 1,...]

Let's calculate some of the convergents for φ:

*p*_{0}/*q*_{0} = 1 = 1/1

*p*_{1}/*q*_{1} = 1 + 1/1 = 2/1

*p*_{2}/*q*_{3} = 1 + 1/(1 + 1/1) = 3/2

and the sequence continues:

i: 0 1 2 3 4 5 6 7 8
---
P_{i} 1 2 3 5 8 13 21 34 55
---
Q_{i} 1 1 2 3 5 8 13 21 34

You may recognize these as the Fibonacci Numbers, *f*_{i}. Incidentally, this demonstrates that

lim_{n→∞} *f*_{n+1}/*f*_{n} = φ.

Cool, huh?! If any of this interests you, you might also find Benet's Formula for *f*_{k} intriguing.

**The Magic Box**

Ok, time to talk convergents. You may already know that one of the reasons these continued fractions are so great is that the sequence {*p*_{n}/*q*_{n}} for a given real number α forms the sequence of best rational approximations to α. That is, for any denominator *q*_{k}, the corresponding *p*_{k} is such that |*p*_{k} - α*q*_{k}| is the smallest it can be.

There are any number of interesting theorems concerning these best approximations. The interested reader is encouraged to seek these out in any good number theory book. (I've listed some below.)

With brute calculation, let's form a table of convergents *p*_{n}/*q*_{n} for an arbitrary continued fraction, say √2 = [1; 2, 2, ...]:

a_{i} 1 2 2 2 2 ...
--
P_{i} (0 1) 1 3 7 17 41 ...
--
Q_{i} (1 0) 1 2 5 12 29 ...

In fact, it turns out that given the terms {a_{i}} of a continued fraction, the convergents can always be calculated using the recurrence relations:

*p*_{k+1} = a_{k+1}*p*_{k} + *p*_{k-1}, and

*q*_{k+1} = a_{k+1}*q*_{k} + *q*_{k-1}

...which hold for all *i* provided we let:

*p*_{-2} = *q*_{-1} = 0 and

*p*_{-1} = *q*_{-2} = 1

...as may be proved by induction. These recurrence relations make calculating convergents so easy (once you get the hang of it) that the chart above is often referred to as the Magic Box.

**Non-Simple Continued Fractions**

To put it simply, a non-simple continued fraction is any in which numbers other than one occur in the numerators of the expansion. They are much harder than SCFs! I don't enough mathematics to really understand them, but some of the sources below have information about them. However, they result in some pretty darn cool formulae, many discovered by Ramanujan.

**References**

MathWorld. "Continued Fractions." See http://mathworld.wolfram.com/ContinuedFraction.html.

Leveque, James. __Fundamentals of Number Theory__. See http://www.amazon.com/exec/obidos/tg/detail/-/0486689069/

qid=1074367205//ref=sr_8_xs_ap_i0_xgl14/002-8476672-9958465?v=glance&s=books&n=507846.

Davenport, H. The Higher Arithmetic. See http://www.amazon.com/exec/obidos/tg/detail/-/0486689069/

qid=1074367205//ref=sr_8_xs_ap_i0_xgl14/002-8476672-9958465?v=glance&s=books&n=507846.

Most information in the writeup comes from personal knowledge gleaned from various sources over the years. However, the above references are either very helpful, well-written, highly-recommended, or several of these things.