**DiscreteMath****`****RSolve****`**

A recurrence or difference equation specifies a relationship between different values of an unknown sequence. For example, the equation a[n]==a[n-1]+a[n-2] specifies that in the unknown sequence a[n], the sum of the two previous terms gives the next term. There may be many sequences that satisfy a given recurrence equation. If you specify the appropriate initial conditions and the equation is sufficiently well behaved, only one solution sequence will exist. Thus, if you specify the initial conditions a[0]==a[1]==1, the equation above has only one solution, namely, the sequence

called Fibonacci numbers.

Solving recurrence equations.

RSolve computes the solution to the given equation using the method of generating functions. The form of the equations given in RSolve is similar to the form used in the built-in DSolve. You can give a single equation, equations with initial conditions or several equations. The solution is returned in the form of a list of replacement rules.

When initial conditions are specified, the range of integers n for which the recurrence equations are valid is inferred from the initial conditions. When initial conditions are not specified, the equations are assumed to be valid for n>=0.

This loads the package.
In[1]:= **<<DiscreteMath`RSolve`**

The solution to this recurrence equation is an exponential. The initial value of the solution sequence is left unspecified. The constant C[1] may be specified using the option RSolveConstants.
In[2]:= **RSolve[a[n+1] == 2 a[n], a[n], n]**

Out[2]=

This specifies an initial value of

.
In[3]:= **RSolve[{a[n+1] == 2 a[n], a[0] == 5},**

a[n], n]

Out[3]=

This is the recursion relation satisfied by the Fibonacci numbers. The initial conditions specify that the first two terms in the solution should be equal to

.
In[4]:= **RSolve[{a[n] == a[n-1] + a[n-2],**

a[0] == a[1] == 1}, a[n], n]

Out[4]=

Here are the first

terms in the solution.
In[5]:= **Table[(a[n] /. %)[[1]], {n, 0, 10}] // Expand**

Out[5]=

This solves a pair of coupled equations. Notice that it is possible to get the solution in pure-function form, by specifying

a,b rather than

a[n],b[n]

.
In[6]:= **RSolve[{a[n+1] - 3 b[n] - 4 a[n] == 1,**

a[n+1] + b[n+1] + b[n] == n,

a[0] == b[0] == 0},

{a, b}, n]

Out[6]=

RSolve can solve any linear constant coefficient equation, as well as systems of such equations. It can also solve two types of linear variable coefficient equations. The first type is a first-order homogeneous equation that has coefficients that are rational functions of . The second kind of equation is one for which the solution grows slower than for any constant and DSolve

can solve the associated differential equation.

This is a linear equation with variable coefficients.
In[7]:= **RSolve[{**

a[0] == a[1] == 2,

(n+1) (n+2) a[n+2] - 2 (n+1) a[n+1] -

3 a[n] == 0},

a[n], n]

Out[7]=

RSolve can also solve nonlinear equations when the nonlinearity comes from a convolution. The solution to this recurrence equation is the sequence of Catalan numbers.
In[8]:= **RSolve[{c[n+1] == Sum[c[k] c[n-k], {k, 0, n}],**

c[0] == 1}, c[n], n]

Out[8]=

The function is called the generating function of the solution . The exponential generating function of the sequence is the function . For example, is the generating function of the sequence and the exponential generating function of the constant sequence

.

Generating functions of sequences.

This computes

, which is simply a geometric series.
In[9]:= **PowerSum[1, {z, n, 0}]**

Out[9]=

This computes the generating function of the sequence of squares of integers.
In[10]:= **PowerSum[n^2, {z, n, 0}]**

Out[10]=

This confirms that the coefficients of the series expansion of the function areX the squares of the integers.
In[11]:= **CoefficientList[Normal[**

Series[%, {z, 0, 10}]], z]

Out[11]=

This exponential generating function is simply the Taylor series for the exponential.
In[12]:= **ExponentialPowerSum[1, {z, n}]**

Out[12]=

Here is the exponential generating function of the sequence of squares of integers.
In[13]:= **ExponentialPowerSum[n^2, {z, n, 0}]**

Out[13]=

This computes the exponential power sum for a series that has a different form when is odd and even. The function Even is provided in the package. It is equivalent to the built-in EvenQ

, except that it does not evaluate when its argument is symbolic.
In[14]:= **ExponentialPowerSum[**

n^2 + 4 n If[Even[n], 2^n, 3^n] + 1,

{z, n, 0}]

Out[14]=

Generating functions for the solutions to recurrence equations.

The solution to the given recurrence equation is the sequence of Fibonacci numbers. Thus, this gives the generating function for this sequence.
In[15]:= **GeneratingFunction[**

{a[n] == a[n-1] + a[n-2],

a[0] == a[1] == 1}, a[n], n, z]

Out[15]=

This recurrence equation gives the sequence of Bernoulli numbers.
In[16]:= **ExponentialGeneratingFunction[**

Sum[Binomial[n, k] B[k], {k, 0, n}] ==

B[n] + If[n==1, 1, 0],

B[n], n, z]

Out[16]=

This computes a list of coefficients in the power series of the generating function just computed and then cancels a factor of from the

term.
In[17]:= **CoefficientList[**

Normal[Series[%[[1,1]], {z, 0, 10}]], z] *

Table[n!, {n, 0, 10}]

Out[17]=

The resulting list contains Bernoulli numbers.
In[18]:= **Table[BernoulliB[n], {n, 0, 10}]**

Out[18]=

Coefficients of Laurent series.

This gives the coefficient of in the Laurent series of

.
In[19]:= **SeriesTerm[1/((x-2) x^2 ), {x, 0, -2}]**

Out[19]=

The coefficient of a series can be computed for a general value of . For this series, the value of the coefficient depends on whether

is negative.
In[20]:= **SeriesTerm[1/(1-x), {x, 0, n}]**

Out[20]=

Here is another general coefficient. The result involves the built-in conditional If.
In[21]:= **SeriesTerm[1/(x - x^3), {x, 0, n}]**

Out[21]=

Since we have specified that only positive

are to be considered, this answer is much simpler.
In[22]:= **SeriesTerm[1/(x - x^3), {x, 0, n}, Assumptions -> {n >= 0}]**

Out[22]=

Options for RSolve. The second group can also be used for SeriesTerm.

The option Method for RSolve gives the method to be used in solving the given recurrence equation. The default value of Automatic specifies that the method of ordinary generating functions (MethodGF) should be used first. If this fails, the method of exponential generating functions (MethodEGF) is used. MethodGF succeeds when either the solution grows subexponentially and DSolve can solve the associated differential equation, or the equation is homogeneous first order and its coefficients are rational functions of . When neither of these is true, you can often save time by specifying Method

->MethodEGF.

This solution grows faster than exponentially and the equation is inhomogeneous, so MethodGF failed.
In[23]:= **Timing[**

RSolve[{T[0] == 5, 2 T[n]==n T[n-1]+ 3 n!},

T[n], n]]

Out[23]=

Now RSolve uses MethodEGF only, so the solution is obtained more quickly.
In[24]:= **Timing[**

RSolve[{T[0] == 5,2 T[n] == n T[n-1] + 3 n!},

T[n], n, Method -> MethodEGF]]

Out[24]=

There are two options that can be used in both RSolve and SeriesTerm. The options IntegerFunctions and SpecialFunctions control the form in which the answer is expressed. Integer functions such as Mod, Even, and Odd are used when IntegerFunctions->True. Special functions such as Legendre polynomials are used when SpecialFunctions->True.

Here the Laurent series coefficient is expressed in terms of Even.
In[25]:= **SeriesTerm[1/(1 - x^4), {x, 0, n}, Assumptions -> {n >= 0}]**

Out[25]=

After specifying IntegerFunctions->False, the result is given in a purely algebraic form.
In[26]:= **SeriesTerm[1/(1 - x^4), {x, 0, n},**

IntegerFunctions -> False, Assumptions -> {n >= 0}]

Out[26]=

This Laurent series coefficient is expressed using Mod.
In[27]:= **SeriesTerm[1/(1 + x^4), {x, 0, n}, Assumptions -> {n >= 0}]**

Out[27]=

IntegerFunctions->False causes a purely algebraic expression to be returned.
In[28]:= **SeriesTerm[1/(1 + x^4), {x, 0, n},**

IntegerFunctions -> False, Assumptions -> {n >= 0}]

Out[28]=

The solution to this equation uses Legendre polynomials.
In[29]:= **RSolve[{P[0] == 1, P[1] == x,**

(n+1) P[n+1] - (2 n + 1) x P[n] +

n P[n-1] == 0}, P[n], n]

Out[29]=

Setting SpecialFunctions->False gives a solution in terms of HypergeometricPFQ.
In[30]:= **RSolve[{P[0] == 1, P[1] == x,**

(n+1) P[n+1] - (2 n + 1) x P[n] +

n P[n-1] == 0}, P[n], n,

SpecialFunctions -> False]

Out[30]=

Options for GeneratingFunction and ExponentialGeneratingFunction.