6.13.3  Values of a recurrence relation or a system: rsolve

(See also Section 6.13.2.)

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 doesn’t 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.
  Input:
  rsolve(u(n+1) = 2*u(n) + n, u(n), u(0)=3)
  Output:

  ⎡ ⎣

  −n+4· 2n−1

  ⎤ ⎦

• Find u_n, given that u_n+1 = 2u_n + n and u₁² = 1.
  Input:
  rsolve(u(n+1) = 2*u(n) + n, u(n), u(1)^2 = 1)
  Output:

  ⎡ ⎢ ⎢ ⎣

  −n+

  3 2

  · 2n−1,−n+

  1 2

  · 2n−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.
  Input:
  rsolve(u(n+1) = 2*u(n) + n*3^n,u(n), u(0)=3)
  Output:

  ⎡ ⎣

  n· 3n+6· 2n−3· 3n

  ⎤ ⎦

• Find u_n, given that u_n+1 = (u_n − 1)/(u_n −2) and u₀ = 4.
  Input:
  rsolve(u(n+1) = (u(n)-1)/(u(n)-2),u(n), u(0)=4)
  Output:

  ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣

  ⎛ ⎜ ⎝ 20  √ 5 +60 ⎞ ⎟ ⎠ ⎛ ⎜ ⎜ ⎝ √ 5 −3 2 ⎞ ⎟ ⎟ ⎠ n   +60  √ 5 −140 40  ⎛ ⎜ ⎜ ⎝ √ 5 −3 2 ⎞ ⎟ ⎟ ⎠ n   +20  √ 5 −60

  ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦

• Find u_n given that u_n+1 = u_n + u_n−1 with u₀ = 0, u₁=1.
  Input:
  rsolve(u(n+1) = u(n) + u(n-1), u(n), u(0) = 0, u(1) = 1)
  Output:

  ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣

  −

  √ 5 5

  ⎛ ⎜ ⎜ ⎝

  − √ 5 +1 2

  ⎞ ⎟ ⎟ ⎠

  n

  +

  1 5

  √

  5

  ⎛ ⎜ ⎜ ⎝

  √ 5 +1 2

  ⎞ ⎟ ⎟ ⎠

  n

  ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦

• To 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, v₀ = 1.
  Input:
  rsolve([u(n+1) = u(n) + v(n), v(n+1) = u(n) - v(n)], [u(n),v(n)], [u(0)=1, v(0)=1])
  Output:

  ⎡ ⎢ ⎢ ⎢ ⎢ ⎣

  1 2   ⎛ ⎜ ⎝ − √ 2 +1 ⎞ ⎟ ⎠ ⎛ ⎜ ⎝ − √ 2 ⎞ ⎟ ⎠ n+1−1   + 1 2   ⎛ ⎜ ⎝ √ 2 +1 ⎞ ⎟ ⎠ · 2 n+1−1 2   1 2   ⎛ ⎜ ⎝ − √ 2 ⎞ ⎟ ⎠ n+1−1   + 1 2 · 2 n+1−1 2

  ⎤ ⎥ ⎥ ⎥ ⎥ ⎦