Difference Equations

and

Recursive Relations

0-400

Number theory index

History Topics Index

Major contributors to the theory of difference equations and recursive relations during this time period between 0 and 400 were Heron, Theon of Smyrna and Diophantus.

Heron is known for Heron's formula for finding the approximate value of the radical of a positive number a, given by:

xn+1 = ( xn + a/xn )/2

This formula is a special case of Newton's formula: 

xn+1 = xn - f(xn)/f'(xn)

Theon of Smyrna is also known for finding the approximate value of the radical of a positive number a, but his finding was based on the use of a linear system and radical numbers. His greatest accomplishment was his procedure for obtaining closer and closer approximations of radical 2. Theon's procedure working with radical 2 involved two sequences of numbers, the side numbers and the diagonal numbers.

We start with two numbers, one is the first side and is denoted by x_1, and the other is the first diagonal and is indicated by y_1. The second side (x₂) and the second diagonal (y₂) are formed from the first side and diagonal, then the third side (x₃) and the third diagonal (y₃) are obtained from the second, and so on, according to the following formulas:

x2 = x1 + y1	y2 = 2x1 + y1
x3 = x2 + y2	y3 = 2x2 + y2
......	.......

In general, x_n and y_n are obtained from the previous pair of side and diagonal numbers by the formula:

xn = xn-1 + yn-1             yn = 2xn-1 + yn-1

The names side numbers and diagonal numbers give a clue that the quotients, y₁ / x₁ of the associated pairs of these numbers comes to approximate the ratio of the diagonal of a square to its side:

y₁ / x₁ = 1,           y₂ / x₂ = 3/2,             y₃ / x₃ = 7/5,           y₄ / x₄ = 17/12,        .....

This follows the relation below:

y_n ² = 2x_n ²  + (-1) ⁿ   = 2x_n ²  1

If this relation is true, then it implies that:

(y_n/ x_n)² =  2 + (-1) ⁿ  (1 / x_n)²  = 2  (1 / x_n)²

This equation is known as invariant and is an extremely useful formula in the work pertaining to recursive relations.

Since the value of (1 / x_n)² can be made as small as we would like just by taking n large enough, it seems that the following ratio:

tends to remain near some fixed number for large n.

This procedure for radical 2 can be applied to any positive integer a. The general formula now becomes:

xn = xn-1 + yn-1       yn = axn-1 + yn-1

We see that:

y_n ² = (ax_n-1+ y_n-1 ) ²   = a²x_n-1 ² + 2ax_n-1  y_n-1 + y_n-1 ²
ax_n ² = a(x_n-1 + y_n-1)²  = ax_n-1 ² + 2ax_n-1 y_n-1 + ay_n-1 ²

By subtracting ax_n ²from y_n ²   we get :

y_n ²- ax_n ² = (a²-a) x_n-1 ² + (1-a) y_n-1 ²
            = (1-a) (y_n-1 ² -ax_n-1 ² )

What was achieved in the previous equation is that y_n ²- ax_n ²  has been represented by an expression of the same form. Next we will replace n with n-1 and we will end up with a chain of equalities as follows:

y_n ²- ax_n ² =  (1-a) (y_n-1 ² - ax_n-1 ² )
               =  (1-a)² (y_n-2 ² - ax_n-2 ² )
               =  (1-a)³ (y_n-3 ² - ax_n-3 ² )
……….. 

y_n ²- ax_n ² =  (1-a)^n-1 (y₁ ² - ax₁ ² )

Therefore we get:

(y_n / x_n )² = a + [(1-a)^n-1 (y₁ ² - ax₁ ² )] / x_n ²     n>2

One example of this can be shown through the discussion of radical 3. If we allow x₁= 1 and y₁= 2 to be the initial side and diagonal numbers, then we arrive at the solution:

(y_n / x_n )² = 3 + ((-2)^n-1 ) / x_n ²      n>2

Diophantus was responsible for using recursive relations to solve the Diophantine equations. Diophantus was not the first person to solve indeterminate problems of second degree. These problems were a common type of mathematical recreation long before his time. Aryabhata and Brahmagupta were two people who heavily contributed to the study of indeterminate equations, which was Diophantus's favorite subject. Aryabhata and Brahmagupta repeated many of Diophantus's problems however their approach was different. Today, in honor of Diophantus, any equation with one of more unknowns that is to be solved for integral values of the unknowns is called a Diophantine equation.

Diophantus proved that the linear diophantine equation ax + by = c has a solution if and only if d/c, where d = gcd (a,b).  He knew that there were integers r and s for which a = dr and b = ds. If a solution of ax + by = c did exist, so that ax₀ + by₀ = c fo a suitable x₀ and y₀, then:

c =  ax₀ + by₀ = dr x₀ + dsy₀ = d(rx₀ + sy₀)

which simply states that d/c. Conversely, we assume that d/c, say c = dt. Now, integers x₀ and y₀ can be found satisfying dax₀ + by₀ . When this relation is multiplied by t, we get:

c = dt = (ax₀ + by₀ )t = a(tx₀ ) + b(ty₀ )

Therefore, this diopantine equation ax + by = c has x = tx₀ and y = ty₀ as a particular solution.

There is a theorem that takes this a step further and states that if x₀, y₀ is any particular solution of this equation, then all other solutions are given by:

x = x₀ + (b/d)t                y = y₀ - (a/d)t

for some integer t.
See also   Monkey  and  Coconut  Problem  and  DiophantineEquation