How to Solve Recurrence Relations

Simple methods to help you conquer recurrence relations

In trying to find a formula for some mathematical sequence, a common intermediate step is to find the n^th 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 n^th 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

Method 1 of 5:

Arithmetic

Download Article

^{[1]XResearch source}
Advertisement
^{[2]XResearch source}
Write the closed-form formula for an arithmetic sequence, possibly with unknowns as shown.^{[3]XResearch source}
In this case, since 5 was the 0^th term, the formula is a_n = 5 + 3n. If instead, you wanted 5 to be the first term, you would get a_n = 2 + 3n.

Method 2

Method 2 of 5:

Geometric

Download Article

Write the closed-form formula for a geometric sequence, possibly with unknowns as shown.
In this case, since 3 was the 0^th term, the formula is a_n = 3*2ⁿ. If instead, you wanted 3 to be the first term, you would get a_n = 3*2^(n-1).^{[4]XResearch source}

Method 3

Method 3 of 5:

Polynomial

Download Article

given by the recursion a_n = a_n-1 + n² - 6n.^{[5]XResearch source}
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.^{[6]XResearch source}
In this example, p is quadratic, so we will need a cubic to represent the sequence a_n.^{[7]XResearch source}
Any four will do, so let's use terms 0, 1, 2, and 3. Running the recurrence backwards to find the -1^th term might make some calculations easier, but isn't necessary.
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.

Method 4

Method 4 of 5:

Linear

Download Article

This is the first method capable of solving the Fibonacci sequence in the introduction, but the method solves any recurrence where the n^th 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, ....^{[8]XResearch source}
This is found by replacing each a_n in the recurrence by xⁿ and dividing by x^(n-k) leaving a monic polynomial of degree k and a nonzero constant term.^{[9]XResearch source}
Solve the characteristic polynomial. In this case, the characteristic has degree 2 so we can use the quadratic formula to find its roots.^{[10]XResearch source}
4
Any expression of the form shown satisfies the recursion. The c_i are any constants and the base of the exponents are the roots to the characteristic found above. This can be verified by induction.^{[11]XResearch source}
- If the characteristic has a multiple root, this step is modified slightly. If r is a root of multiplicity m, use (c₁rⁿ + c₂nrⁿ + c₃n²rⁿ + ... + c_mn^m-1rⁿ) instead of simply (c₁rⁿ). For example, the sequence starting 5, 0, -4, 16, 144, 640, 2240, ... satisfies the recursive relationship a_n = 6a_n-1 - 12a_n-2 + 8a_n-3. The characteristic polynomial has a triple root of 2 and the closed form formula a_n = 5*2ⁿ - 7*n*2ⁿ + 2*n²*2ⁿ.
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 0^th and 1^st to avoid having to raise an irrational number to a high power.

Method 5

Method 5 of 5:

Generating Functions

Download Article

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.^{[12]XResearch source}
A generating function is simply a formal power series where the coefficient of xⁿ is the n^th term of the sequence.^{[13]XResearch source}
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.
^{[14]XResearch source}
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.

Community Q&A

Search

Add New Question

Question
If a sequence is defined recursively by f(0)=2 and f(n+1)=-2f(n)+3 for n0, then f(2) is equal to what?
Community Answer
For n = 0 f(0+1) = - 2 f(0) + 3 f(1) = - 2(2) + 3 So f(1) = - 4 + 3 = -1For n = 1 f(1+1) = -2 f(1) + 3 f(2) = -2 (-1) + 3 So f(2) = 2 + 3 = 5
Thanks! We're glad this was helpful.
Thank you for your feedback.
If How.com.vn has helped you, please consider a small contribution to support us in helping more readers like you. We’re committed to providing the world with free how-to resources, and even $1 helps us in our mission.Support How.com.vn
Yes No
Not Helpful 6 Helpful 6
Question
Is there a sequence that has second differences which produces a geometric sequence? If there is, what is name of the sequence and how can I derive the formula for the nth term in that sequence?
Community Answer
If you start with a geometric sequence, then all its differences will be geometric sequences (constant multiple of the original). The second differences of a linear sequence vanish, so you can add a linear sequence to any other sequence without changing its second differences. I don't believe there's a special name for the sum of a geometric and a linear sequence, but the formula is (a * b^n) + (c * n) + d for some constants a, b, c, and d, and they have your desired property.
Thanks! We're glad this was helpful.
Thank you for your feedback.
If How.com.vn has helped you, please consider a small contribution to support us in helping more readers like you. We’re committed to providing the world with free how-to resources, and even $1 helps us in our mission.Support How.com.vn
Yes No
Not Helpful 0 Helpful 0

Ask a Question

200 characters left

Include your email address to get a message when this question is answered.

Submit

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.
Thanks
Helpful0 Not Helpful0
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.
Thanks
Helpful0 Not Helpful0
"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 F_n of Fibonacci numbers is defined by the recurrence relation
- F_n= F_n-1 + F_n-2 with seed values F₁ = 1, F₂ = 1 or F₀ = 0, F₁ = 1.
- The limit as n increases of the ratio F_n/F_n-1 is known as the Golden Ratio or Golden Mean or Phi (Φ), and so is the limit as n increases of the ratio F_n-1/F_n."¹
Thanks
Helpful0 Not Helpful0