How to Solve Recurrence Relations

Five Methods:ArithmeticGeometricPolynomialLinearGenerating Functions

In trying to find a formula for some mathematical sequence, a common intermediate step is to find the nth term, not as a function of n, but in terms of earlier terms of the sequence. For example, while it'd be nice to have a closed form function for the nth term of the Fibonacci sequence, sometimes all you have is the recurrence relation, namely that each term of the Fibonacci sequence is the sum of the previous two terms. This article will present several methods for deducing a closed form formula from a recurrence.

Method 1
Arithmetic

  1. Image titled Solve Recurrence Relations Step 1
    1
    Consider an arithmetic sequence such as 5, 8, 11, 14, 17, 20, ....
  2. Image titled Solve Recurrence Relations Step 2
    2
    Since each term is 3 larger than the previous, it can be expressed as a recurrence as shown.
  3. Image titled Solve Recurrence Relations Step 3
    3
    Recognize that any recurrence of the form an = an-1 + d is an arithmetic sequence.
  4. 4
    Write the closed-form formula for an arithmetic sequence, possibly with unknowns as shown.

  5. 5
    Solve for any unknowns depending on how the sequence was initialized. In this case, since 5 was the 0th term, the formula is an = 5 + 3n. If instead, you wanted 5 to be the first term, you would get an = 2 + 3n.

Method 2
Geometric

  1. Image titled Solve Recurrence Relations Step 6
    1
    Consider a geometric sequence such as 3, 6, 12, 24, 48, ....
  2. Image titled Solve Recurrence Relations Step 7
    2
    Since each term is twice the previous, it can be expressed as a recurrence as shown.
  3. Image titled Solve Recurrence Relations Step 8
    3
    Recognize that any recurrence of the form an = r * an-1 is a geometric sequence.
  4. Image titled Solve Recurrence Relations Step 9
    4
    Write the closed-form formula for a geometric sequence, possibly with unknowns as shown.
  5. Image titled Solve Recurrence Relations Step 10
    5
    Solve for any unknowns depending on how the sequence was initialized. In this case, since 3 was the 0th term, the formula is an = 3*2n. If instead, you wanted 3 to be the first term, you would get an = 3*2(n-1).

Method 3
Polynomial

  1. 1
    Consider the sequence 5, 0, -8, -17, -25, -30, ... given by the recursion an = an-1 + n2 - 6n.

  2. Image titled Solve Recurrence Relations Step 12
    2
    Any recursion of the form shown, where p(n) is any polynomial in n, will have a polynomial closed form formula of degree one higher than the degree of p.
  3. Image titled Solve Recurrence Relations Step 13
    3
    Write the general form of a polynomial of the required degree. In this example, p is quadratic, so we will need a cubic to represent the sequence an.
  4. Image titled Solve Recurrence Relations Step 14
    4
    Since a general cubic has four unknown coefficients, four terms of the sequence are required to solve the resulting system. Any four will do, so let's use terms 0, 1, 2, and 3. Running the recurrence backwards to find the -1th term might make some calculations easier, but isn't necessary.
  5. Image titled Solve Recurrence Relations Step 15
    5
    Either Solve the resulting system of deg(p)+2 equations in deg(p)=2 unknowns or Fit a Lagrange polynomial to the deg(p)+2 known points.
    • If the zeroth term was one of the terms you used to solve for the coefficients, you get the constant term of the polynomial for free and can immediately reduce the system to deg(p)+1 equations in deg(p)+1 unknowns as shown.
      Image titled Solve Recurrence Relations Step 16
  6. Image titled Solve Recurrence Relations Step 17
    6
    Present the closed formula for an as a polynomial with known coefficients.

Method 4
Linear

  1. Image titled Solve Recurrence Relations Step 18
    1
    This is the first method capable of solving the Fibonacci sequence in the introduction, but the method solves any recurrence where the nth term is a linear combination of the previous k terms. So let's try it on the different example shown whose first terms are 1, 4, 13, 46, 157, ....
  2. Image titled Solve Recurrence Relations Step 19
    2
    Write the characteristic polynomial of the recurrence. This is found by replacing each an in the recurrence by xn and dividing by x(n-k) leaving a monic polynomial of degree k and a nonzero constant term.
  3. Image titled Solve Recurrence Relations Step 20
    3
    Solve the characteristic polynomial. In this case, the characteristic has degree 2 so we can use the quadratic formula to find its roots.
  4. Image titled Solve Recurrence Relations Step 21
    4
    Any expression of the form shown satisfies the recursion. The ci are any constants and the base of the exponents are the roots to the characteristic found above. This can be verified by induction.
    • If the characteristic has a multiple root, this step is modified slightly. If r is a root of multiplicity m, use (c1rn + c2nrn + c3n2rn + ... + cmnm-1rn) instead of simply (c1rn). For example, the sequence starting 5, 0, -4, 16, 144, 640, 2240, ... satisfies the recursive relationship an = 6an-1 - 12an-2 + 8an-3. The characteristic polynomial has a triple root of 2 and the closed form formula an = 5*2n - 7*n*2n + 2*n2*2n.
  5. Image titled Solve Recurrence Relations Step 22
    5
    Find the ci that satisfy the specified initial conditions. As with the polynomial example, this is done by creating a linear system of equations from the initial terms. Since this example has two unknowns, we need two terms. Any two will do, so take the 0th and 1st to avoid having to raise an irrational number to a high power.
  6. Image titled Solve Recurrence Relations Step 23
    6
    Solve the resulting system of equations.
  7. Image titled Solve Recurrence Relations Step 24
    7
    Plug the resulting constants into the general formula as the solution.

Method 5
Generating Functions

  1. Image titled Solve Recurrence Relations Step 25
    1
    Consider the sequence 2, 5, 14, 41, 122 ... given by the recursion shown. This cannot be solved by any of the above methods, but a formula can be found by using generating functions.
  2. Image titled Solve Recurrence Relations Step 26
    2
    Write the generating function of the sequence. A generating function is simply a formal power series where the coefficient of xn is the nth term of the sequence.
  3. Image titled Solve Recurrence Relations Step 27
    3
    Manipulate the generating function as shown. The objective in this step is to find an equation that will allow us to solve for the generating function A(x). Extract the initial term. Apply the recurrence relation to the remaining terms. Split the sum. Extract constant terms. Use the definition of A(x). Use the formula for the sum of a geometric series.
  4. Image titled Solve Recurrence Relations Step 28
    4
    Find the generating function A(x).
  5. Image titled Solve Recurrence Relations Step 29
    5
    Find the coefficient of the xn in A(x). The methods for doing this will vary depending on exactly what A(x) looks like, but the method of partial fractions, combined with knowing the generating function of a geometric sequence, works here as shown.
  6. Image titled Solve Recurrence Relations Step 30
    6
    Write the formula for an by identifying the coefficient of xn in A(x).

Tips

  • Induction is also a popular technique. It's often easy to prove by induction that a specified formula satisfies a specified recursion, but the problem is this requires guessing the formula in advance.
  • Some of these methods are computationally intensive with many opportunities to make a stupid mistake. It's good to check the formula against a few known terms.
  • "In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
    • The Fibonacci spiral: an approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling; this one uses squares of sizes 1, 1, 2, 3, 5, 8, 13, 21, and 34.
    • By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.
    • In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
    • Fn= Fn-1 + Fn-2 with seed values F1 = 1, F2 = 1 or F0 = 0, F1 = 1.
    • The ratio of Fn/Fn-1 is known as the Golden Ratio or Golden Mean or Phi (Φ), and so is the ratio Fn-1/Fn."1

Sources and Citations

Article Info

Featured Article

Categories: Featured Articles | Mathematics