A means of generating an integer sequence. One starts with a small number of initial values, and then applies a recurrence rule. See, for example, the Fibonacci sequence.

--back to combinatorics--

Said another way, a recurrence relation is a function that is defined in terms of itself. For example, a function to generate the fibonacci numbers mentioned by artermis entreri above is defined as:

general case:
F(n) = F(n - 1) + F(n - 2), for n > 2

base cases:
F(1) = 1
F(2) = 1

One use of recurrence relations is in determining the complexity of algorithms.

Solving univariate homogeneous linear recurrence relations

Warning: This node uses a fair bit of HTML mathematical entities. It may not render correctly in your browser; it's been checked in Mozilla 1.0 and 1.1.

The most general form of such a beast is
        Fn = an-1Fn-1 + an-2Fn-2 + ...
To solve a relation of this form, we identify each Fn with xn to form a polynomial
        xn = an-1xn-1 + an-2xn-2 + ...
Now if we let d be the largest integer such that an-d ≠ 0, then we can divide the whole equation through by xn-d to reduce it down to a simpler form.

Next, we need to find the roots of a polynomial). This will give us a set of d roots:

        { r0, ..., rd-1 }

From here, it gets very messy, so we will only look at the case d = 2. Wondering why this method works? The explanation is quite convoluted, involving generating functions and "intelligent guessing", so we won't go into it here. It should be covered in an elementary undergraduate-level textbook on discrete mathematics.

Depending on the nature of the roots r0, r1, there are 2 cases to consider.

Case 1: r0 ≠ r1

In this case, the form of the solution will be
        Fn = Ar0n + Br1n
A, B are constants that depend on the initial values of Fn.

Case 2: r0 = r1

In this case, the form of the solution will be
        Fn = Ar0n + Bnr0n
(Note the 'n' in the second term!). A, B are constants that depend on the initial values of Fn.

The insightful reader may note that we might get complex roots. This is not a problem; we just use Case 1, and get an answer that involves sine and cosine terms.


A worked example:
        Fn = Fn-1 + 2Fn-2
First, we get the expression
        xn = xn-1 + 2xn-2
which is equivalent to
        x2 = x + 2
The roots of this (given by the quadratic formula) are
        x = 2    and    x = -1
Therefore, using Case 1, the form of the solution is
        Fn = A(2)n + B(-1)n
Now, imagine our initial conditions are
        F0 = 1    and    F1 = 1
We get the two simultaneous equations
        1 = A + B    and    1 = 2A - B
Solving these using standard high-school techniques, we get
        A = 2/3    and    B = 1/3
Finally, our complete closed-form solution is
        Fn = (2/3)2n + (2/3)(-1)n

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