Difference Equations
and
Recursive Relations

Pythagoras, Archimedes, and Euclid
600 - 0 B.C.



Difference Equations
Index
URI Mathematics
Department


Difference equations and recursive relations and their properties were first studied extensively by the ancient Greek mathematicians such as Pythagoras, Archimedes, and Euclid.

Pythagoras

"What you take to be 4 is 10, a perfect triangle and our oath."

Triangular Numbers

One of Pythagoras's major contributions to this topic was his idea of triangular numbers.  Triangular numbers are formed by the equation where tn is the nth triangular number:

 tn = tn-1 + n
                = tn-2 + (n-1) + n
                                 = t1 + 2 + 3 + ... + (n-1) + n
                                 = 1 + 2 + 3 + ... + (n-1) + n

This formula tells us we can calculate triangular numbers by adding up consecutive numbers.  For example, the ninth triangular number is equal to:

                                               t9 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
t9 = 45
There is a useful shortcut that can be used to find a large triangular number.  If you want to find the 1000 triangular number, you could add up all the numbers from 1 to 1000.  Or you could use this simpler method:
tn= (n2 +n) ÷ 2
So the 1000th triangular number is:
                  t1000 = (10002 + 1000) ÷ 2
t1000 = 500500

Pythagoras's triangular numbers got that name because that is what you can visualize them as.  Each one, when arranged started at t1 = 1, the first triangular number, will form a equilateral triangle.  The first four triangular numbers would look like the following:






For a more  discussion of Triangular numbers  visit mathworld.wolfram.com

Archimedes

"Give me a place to stand, and I will move the Earth."

Method of Exhaustion

A major contribution from Archimedes is his method of exhaustion.   Archimedes discovered a method of calculating Pi that was used until nineteen centuries later. This method was to inscribe inside and outside a circle a polygon of many sides. The perimeter of the inside polygon would be smaller then p and the outside would be larger then p.  His method would look like this: for regular polygons inscribed in a circle of radius 1, using Si where i are the number of sides Archimedes used:

S6 = 1
to conclude that:
 S12 = Ö(2 - Ö3)
         S24 = Ö(2 - Ö(2 + Ö3))
                  S48 = Ö(2 - Ö(2 + Ö(2 + Ö3)))
                         S96 = Ö(2 - Ö(2 + Ö(2 +Ö(2 + Ö3))))
From these figures, Archimedes obtained a numerical value for p.  He gave the value to be:

p ~ 48S96 ~ 3.14103 ~ 22/7

For a visual representation of the circle with the inscribed polygon and the computation of p check out the University of Utah's math page.

See also Archimedes Algoritam and  Archimedes Recurrence Formula
 
 

Euclid

"There is no royal road to geometry."

Euclid's Algorithm & Continued Fractions

The Euclidean algorithm is an example of a P-problem whose time complexity is bounded by a quadratic function of the length of the input values (Bach and Shallit). Let, then find a number u which divides both a and b (so that a = su and b = tu), then u also divides r since 

Similarly, find a number v which divides b and r (so that  and ), then v divides a since 
Therefore, every common divisor of a and b is a common divisor of b and r, so the procedure can be iterated as follows.
                                                                                           ...

For integers, the algorithm terminates when  divides  exactly, at which point corresponds to the greatest common divisor of a and b. For real numbers, the algorithm yields ei
The origin of continued fractions is traditionally placed at the time of the creation of Euclid's Algorithm.  Euclid's Algorithm, however, is used to find the greatest common denominator (gcd) of two numbers. However, by algebraically manipulating the algorithm, one can derive the simple continued fraction of the rational p/q as opposed to the gcd of p and q. A continued fraction is a fraction of the form:

a0       b1.
          a1    b2    .
                  a2 + ...

A continued fraction that has a definite end is a rational number.  An example of this would be:
Suppose you wish to find the greatest common divisor of 123 and 456. You might proceed as follows:

            (1)  Divide 456 by 123 to get:

3 +  87 .
     123

            (2)  Now divide the new remainder 87 into the previous divisor 123.

3 +         1  .
   1 +  36
         87

            (3) Dividing these numbers and finding the remainder is Euclid's Algorithm, continue until it ends and it looks like:

3 +                       1                 .
     1 +                1            .
       2 +             1            .
            2 +       1     .
               2 +  1 .
                     2

Using Euclid's algorithm is very useful for not only finding the gcd of two numbers, but also for determining continued fractions.
A continued fraction that goes on in a recursive manner is called an irrational number.  A good example of this would be:

To write this in standard notation use the whole numbers and write them in brackets:

[2; 2; 2; 2; 2; . . .]

To find an approximated value for an irrational continued fraction, choose a part in the fraction and choose to end it there.  Then calculate the fraction and that number is your approximation for that continued fraction and irrational number.

For a more in-depth discussion of continued fractions and it's uses visit Cut-The-Knot.com.