6.2.2  Solving a recurrence relation or a system

The seqsolve command finds the terms of a recurrence relation.

• seqsolve takes three arguments:
  • exprs, an expression or list of expressions that define the recurrence relation.
  • vars, a list of the variables used.
  • a, the starting value.
• seqsolve(exprs,vars,a) returns a formula for the nth term of the sequence.

For example, if a recurrence relation is defined by u_n+1= f(u_n,n) with u₀=a, the arguments to seqsolve will be f(x,n), [x,n] and a. If the recurrence relation is defined by u_n+2=g(u_n,u_n+1,n) with u₀=a and u₁=b, the arguments to seqsolve will be g(x,y,n), [x,y,n] and [a,b].

The recurrence relation must have a homogeneous linear part, the nonhomogeneous part must be a linear combination of a polynomials in n times geometric terms in n.

The rsolve command is an alternate way to find the values of a recurrence relation. Note that rsolve is more flexible than seqsolve since:

• The sequence does not have to start with u₀.
• The sequence can have several starting values, such as initial condition u₀²=1, which is why rsolve returns a list.
• The notation for the recurrence relation is similar to how it is written in mathematics.

• rsolve takes three arguments:
  • eqns, an equation or list of equations that define the recurrence relation.
  • fns, the function or list of functions (with their variables) used.
  • startvals, the equation or list of equations for the starting values.
• rsolve(eqns,fns,startvals) returns a list containing a formula for the nth term of the sequence. (If there is more than one sequence, it will return a formula for each one.)

For example, if a recurrence relation is defined by u_n+1=f(u_n,n) with u₀=a, the arguments to rsolve will be u(n+1)=f(u(n),n), u(n) and u(0)=a.

The recurrence relation must either be a homogeneous linear part with a nonhomogeneous part being a linear combination of polynomials in n times geometric terms in n (such as u_n+1=2 u_n+n 3ⁿ), or a linear fractional transformation (such as u_n+1= (u_n−1)/(u_n−2)).

Examples

Find u_n, given that u_n+1=2u_n+n and u₀=3.

Find u_n, given that u_n+1=2u_n+n 3ⁿ and u₀=3.

Find u_n, given that u_n+1=u_n+u_n−1, u₀=0 and u₁=1.

Find u_n and v_n, given that u_n+1=u_n+2v_n, v_n+1= u_n+n+1 with u₀=1, v₀=1.

Find u_n, given that u_n+1=2u_n+n and u₀=3.

Find u_n, given that u_n+1=2u_n+n and u₁²=1.

Note that there are two formulas, since the starting formula u₁²=1 gives two possible starting values: u₁=1 and u₁=2.

Find u_n, given that u_n+1=2u_n+n 3ⁿ and u₀=3.

Find u_n, given that u_n+1=(u_n−1)/(u_n −2) and u₀= 4.

Find u_n given that u_n+1=u_n+u_n−1 with u₀=0, u₁=1.

Find u_n and v_n, given that u_n+1=u_n+v_n, v_n+1= u_n−v_n with u₀=0 and v₀=1.