This is documentation for Mathematica 5, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)

Documentation / Mathematica / The Mathematica Book / Advanced Mathematics in Mathematica / Series, Limits and Residues /

3.6.8 Solving Recurrence Equations

If you represent the n term in a sequence as a[n], you can use a recurrence equation to specify how it is related to other terms in the sequence.

RSolve takes recurrence equations and solves them to get explicit formulas for a[n].

This solves a simple recurrence equation.

In[1]:= RSolve[{a[n] == 2 a[n-1], a[1] == 1}, a[n], n]


This takes the solution and makes an explicit table of the first ten a[n].

In[2]:= Table[a[n] /. First[%], {n, 10}]


Solving a recurrence equation.

This solves a recurrence equation for a geometric series.

In[3]:= RSolve[{a[n] == r a[n-1] + 1, a[1] == 1}, a[n], n]


This gives the same result.

In[4]:= RSolve[{a[n+1] == r a[n] + 1, a[1] == 1}, a[n], n]


This gives an algebraic solution to the Fibonacci recurrence equation.

In[5]:= RSolve[{a[n] == a[n-1] + a[n-2], a[1] == a[2] == 1}, a[n], n]


RSolve can be thought of as a discrete analog of DSolve. Many of the same functions generated in solving differential equations also appear in finding symbolic solutions to recurrence equations.

This generates a gamma function, which generalizes the factorial.

In[6]:= RSolve[{a[n] == n a[n-1], a[1] == 1}, a[n], n]


This second-order recurrence equation comes out in terms of Bessel functions.

In[7]:= RSolve[{a[n + 1] == n a[n] + a[n - 1],
a[1] == 0, a[2] == 1}, a[n], n]


RSolve does not require you to specify explicit values for terms such as a[1]. Like DSolve, it automatically introduces undetermined constants C[i] to give a general solution.

This gives a general solution with one undetermined constant.

In[8]:= RSolve[a[n] == n a[n-1], a[n], n]


RSolve can solve equations that do not depend only linearly on a[n]. For nonlinear equations, however, there are sometimes several distinct solutions that must be given. Just as for differential equations, it is a difficult matter to find symbolic solutions to recurrence equations, and standard mathematical functions only cover a limited set of cases.

Here is the general solution to a nonlinear recurrence equation.

In[9]:= RSolve[{a[n] == a[n + 1] a[n - 1]}, a[n], n]


This gives two distinct solutions.

In[10]:= RSolve[a[n] == (a[n + 1] a[n - 1])^2, a[n], n]


RSolve can solve not only ordinary difference equations in which the arguments of a differ by integers, but also q-difference equations in which the arguments of a are related by multiplicative factors.

This solves the -difference analog of the factorial equation.

In[11]:= RSolve[a[q n] == n a[n], a[n], n]


Here is a second-order -difference equation.

In[12]:= RSolve[a[n] == a[q n] + a[n/q], a[n], n]


Solving systems of recurrence equations.

This solves a system of two coupled recurrence equations.

In[13]:= RSolve[{a[n] == b[n - 1] + n, b[n] == a[n - 1] - n,
a[1] == b[1] == 1}, {a[n], b[n]}, n]


Solving partial recurrence equations.

Just as one can set up partial differential equations that involve functions of several variables, so one can also set up partial recurrence equations that involve multidimensional sequences. Just as in the differential equations case, general solutions to partial recurrence equations can involve undetermined functions.

This gives the general solution to a simple partial recurrence equation.

In[14]:= RSolve[a[i + 1, j + 1] == i j a[i, j], a[i, j], {i, j}]