Any real number x can be represented as a continued fraction as:

                b
                 0
x = a + ----------------------
     0            b
                   1
         a  + ----------------
          1           b
                       2
               a  + ----------
                2
                     a  + ...
                      3

Typesetters hate this form (quite understandably), and prefer to write continued fractions as:

      b    b    b
       0    1    2
a  + ---- ---- ---- ....
 0   a  + a  + a  +
      1    2    3

A simple continued fraction is where all of the bn are all identically equal to 1.

Continued fractions can be used to find best rational estimates for irrational numbers. Functions may also be written as continued fractions, giving successively better rational approximations.

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 a0 = ⌊α⌋
α1 = 1 / (α0 - a0) and a1 = ⌊α1
...
αn = 1 / (αn - 1 - an - 1) and an = ⌊αn

Then, using the notion developed for finite SCFs,

α = limn→∞ [a0; a1, ..., an] = [a0; a1, a2, ...]

The partial quotients [a0; a1, ..., ak] thus form a sequence, commonly denoted pk/qk, and known as the sequence of convergents for α.

Example

Let α = √2. Then:

a0 = ⌊√2⌋ = 1
a1 = ⌊ 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 [a0; a1, ..., ak] 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

x2 + 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 φ:

p0/q0 = 1 = 1/1

p1/q1 = 1 + 1/1 = 2/1

p2/q3 = 1 + 1/(1 + 1/1) = 3/2

and the sequence continues:

i:  0  1  2  3  4  5  6  7  8     
---
Pi   1  2  3  5  8  13 21 34 55 
--- 
Qi   1  1  2  3  5  8  13 21 34 

You may recognize these as the Fibonacci Numbers, fi. Incidentally, this demonstrates that

limn→∞ fn+1/fn = φ.

Cool, huh?! If any of this interests you, you might also find Benet's Formula for fk 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 {pn/qn} for a given real number α forms the sequence of best rational approximations to α. That is, for any denominator qk, the corresponding pk is such that |pk - αqk| 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 pn/qn for an arbitrary continued fraction, say √2 = [1; 2, 2, ...]:

  
ai           1   2   2   2   2  ...
-- 
Pi  (0   1)  1   3   7   17  41   ...
--
Qi  (1   0)  1   2   5   12  29  ... 

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

pk+1 = ak+1pk + pk-1, and
qk+1 = ak+1qk + qk-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.

Log in or register to write something here or to contact authors.