Difference equations and recursive relations have been studied extensively by Fatou and Julia in the case of rational functions in complex domain.  Gaston Julia(1893-1978) and Pierre Fatou (1878-1929) made a fundamental contribution to the study of iterative processes. Their contribution, although regarded as a masterpiece, was largely ignored by the mathematical community until a revival in the late 1970s spawned by the discovery of fractals by Benoit Mandelbrot.

        Given a function f(x) and a starting value x₀one can construct a new value x₁=f(x₀). With some persistence, the next value x₂ is obtained by another application of f: x₂=f(x₁))=f(f(x₀)). This is an iterative process that, generally speaking, generates a sequence x₀, x₁, ... x_k, ..., where x_k is the kth iterate obtained by applying the function f to x₀ k times. The sequence is known as an orbit of its starting point x₀.

        For a given function f, behavior of an orbit very much depends on the selection of the starting point x₀. Following is a rough classification of possible behaviors:
 

The set of points with chaotic orbits is called the Julia set for a given function f.
 
 

        Fractal Curves and Dimension have been studied extensively by Sierpinski and Besicovitch.  Fractals burst into the open in early 1970s. Their breathtaking beauty captivated many a layman and a professional alike. Striking fractal images can often be obtained with very elementary means. However, the definition of fractals is far from being trivial and depends on a formal definition of dimension.

        It takes a few chapters of an Advanced Analysis book to rigorously define a notion of dimension. The important thing is that the notion is not unique and even more importantly, for a given set, various definitions may lead to different numerical results. When the results differ the set is called fractal.

        The topological dimension of a smooth curve is, as one would expect, one and that of a sphere is two, which may seem very intuitive. However, the formal definition was only given in 1913 by the Dutch mathematician L. Brouwer (1881-1966). A (solid) cube has the topological dimension of three because in any decomposition of the cube into smaller bricks there always are points that belong to at least four (3+1) bricks.

        The Brouwer dimension is obviously an integer. The Hausdorff-Besicovitch dimension, on the other hand, may be a fraction. Formal definition of this quantity requires a good deal of the Measure Theory. But fortunately for a class of sets Hausdorff-Besicovitch dimension can be easily evaluated. These sets are known as the self-similar fractals and, because of that ease, the property of self-similarity is often considered to be germane to fractals in general.

        Koch's Snowflake illustrates the idea of self-similarity.  Initially there is an equilateral triangle in the middle of a straight line segment. This combination of four segments form a pattern which serves as a description of an algorithm to be used later on. The secret meaning of the pattern is this:
 
 

        It's possible to formally prove that thus obtained curves converge to a limit curve. This limiting curve is self-similar because it consists of four smaller copies of itself which, in turn, also and naturally consist of four smaller copies of themselves and so on.
 
 

   Morse is the father of Symbolic Dynamics.  The Thue-Morse constant is also called the Parity Constant and is defined by
 
 

and is equal to 0.41245403364... Click here for some application of Thue-Morse sequences to the fractal music. Here P(n) is the parity of n.  The Thue-Morse constant can be written in base 2 by stages by taking the previous iteration a_n , taking the complement , and appending, producing
 

This can be written symbolically as
 
 

with a₀= 0.  Here the complement is the number such that a_n+= 0.11....₂, which can be found from
 
 

.

= 1- a_n- 2^-2n,

and

The regular continued fraction for the Thue-Morse constant is [0 2 2 2 1 4 3 5 2 1 4 2 1 5 44 1 4 1 2 4 1 1 1 5 14 1 50 15 5 1 1 1 4 2 1 4 1 43 1 4 1 2 1 3 16 1 2 1 2 1 50 1 2 424 1 2 5 2 1 1 1 5 5 2 22 5 1 1 1 1274 3 5 2 1 1 1 4 1 1 15 154 7 2 1 2 2 1 2 1 1 50 1 4 1 2 867374 1 1 1 5 5 1 1 6 1 2 7 2 1650 23 1 1 1 2 5 3 84 1 1 1 1284...], and seems to continue with sporadic large terms in suspiscious-looking patterns.
 
 

    In the theory of metric spaces an important part is played by cantraction mappings.  A mapping T of a metric space (M,z) into itself is called a contraction mapping if
 
 

for all elements x,y of M.

        It can be proved that such a mapping always has a unique fixed point, i.e. that there exists a unique x which is an element of M such that

This Important result is called Banach's fixed point theorem.  The proof of this theorem not only establishes the existence and uniqueness of the fixed point; it also prescribes a method of finding it.  If we begin with an arbitrary element x₀ of M and generate a sequence {x_n} by means of the iteration formula

the limit of this sequence is the fixed point of the contraction mapping T.

       The error involved in truncating the iterative process at the nth stage is estimated by the formula

The Banach fixed-point theorem, and its generalization the Shauder fixed-point theorem are used extensively in proving existence theorems for problems in algebra, and the theory of differential and integral equations, and in establishing the convergence of iterative schemes in the numerical analysis of such problems.
 
 

        Khinchin worked extensively withcontinued fractions.  Let
 
 

be the simple continued fraction of a real number x, where the numbers q_i are partial quotients.  Khinchin considered the limit of the geometric mean

as n approaches infinity.  Amazingly enough, this limit is a constant independent of x--except if x belongs to a set of measure 0--given by
 
 

Explicit expressions for K include

For more detailed explanation of this constant click here.
 

        Aleksandr Gelfond wrote an important textbook on Difference Equations and Finite Differences in which he used continued fractions extensively.
 
 

    Maurits Escher was a painter who created paintings using recursive designs.
 

   The following picture is Escher's Eight Heads.
 
 

This picture is titled Reflection in a Glass Ball.

This picture is titled Up and Down.

Visit Algorithm