### 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 un+1= f(un,n) with u0=a, the arguments to seqsolve will be f(x,n), [x,n] and a. If the recurrence relation is defined by un+2=g(un,un+1,n) with u0=a and u1=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 u0.
- The sequence can have several starting values, such as initial condition u02=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 un+1=f(un,n) with u0=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 un+1=2 un+n 3n), or a linear fractional transformation (such as un+1= (un−1)/(un−2)).

#### Examples

Find un, given that un+1=2un+n and u0=3.

seqsolve(2 x+n,[x,n],3)

−n−1+4· 2n |  |  |  |  |  |  |  |  |  |

Find un, given that un+1=2un+n 3n and u0=3.

seqsolve(2 x+n*3^n,[x,n],3)

| ⎛ ⎝ | n−3 | ⎞ ⎠ | · 3n+6· 2n

Find un, given that un+1=un+un−1, u0=0 and u1=1.

seqsolve(x+y,[x,y,n],[0,1])

5

⎛
⎜
⎜
⎝

−

√

5

+1

2

⎞
⎟
⎟
⎠

n

−4

⎛
⎜
⎜
⎝

−

√

5

+1

2

⎞
⎟
⎟
⎠

n

√

5

−5

⎛
⎜
⎜
⎝

−

√

5

+1

2

⎞
⎟
⎟
⎠

n

+5

⎛
⎜
⎜
⎝

√

5

+1

2

⎞
⎟
⎟
⎠

n

+4

⎛
⎜
⎜
⎝

√

5

+1

2

⎞
⎟
⎟
⎠

n

√

5

−5

⎛
⎜
⎜
⎝

√

5

+1

2

⎞
⎟
⎟
⎠

n

20

Find un and vn, given that un+1=un+2vn, vn+1= un+n+1 with u0=1, v0=1.

seqsolve([x+2*y,n+1+x],[x,y,n],[0,1])

⎡
⎢
⎢
⎣

−2 n− | ⎛ ⎝ | −1 | ⎞ ⎠ | n+4· 2n−3

2

,

⎛ ⎝ | −1 | ⎞ ⎠ | n+2· 2n−1

2

⎤
⎥
⎥
⎦

Find un, given that un+1=2un+n and u0=3.

rsolve(u(n+1)=2*u(n)+n,u(n),u(0)=3)

| ⎡ ⎣ | −n+4· 2n−1 | ⎤ ⎦

Find un, given that un+1=2un+n and u12=1.

rsolve(u(n+1)=2*u(n)+n,u(n),u(1)^2=1)

⎡
⎢
⎢
⎣

−n+

3
2

· 2n−1,−n+

1
2

· 2n−1

⎤
⎥
⎥
⎦

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

Find un, given that un+1=2un+n 3n and u0=3.

rsolve(u(n+1)=2*u(n)+n*3^n,u(n),u(0)=3)

| ⎡ ⎣ | n· 3n+6· 2n−3· 3n | ⎤ ⎦

Find un, given that un+1=(un−1)/(un −2) and u0= 4.

rsolve(u(n+1)=(u(n)-1)/(u(n)-2),u(n),u(0)=4)

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣

⎛
⎜
⎝

20

√

5

+60

⎞
⎟
⎠

⎛
⎜
⎜
⎝

√

5

−3

2

⎞
⎟
⎟
⎠

n

+60

√

5

−140

40

⎛
⎜
⎜
⎝

√

5

−3

2

⎞
⎟
⎟
⎠

n

+20

√

5

−60

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦

Find un given that un+1=un+un−1 with u0=0, u1=1.

rsolve(u(n+1)=u(n)+u(n-1),u(n),u(0)=0,u(1)=1)

⎡
⎢
⎢
⎢
⎢
⎢
⎣

−

√

5

5

⎛
⎜
⎜
⎝

−

√

5

+1

2

⎞
⎟
⎟
⎠

n

+

1
5

√

5

⎛
⎜
⎜
⎝

√

5

+1

2

⎞
⎟
⎟
⎠

n

⎤
⎥
⎥
⎥
⎥
⎥
⎦

Find un and vn, given that un+1=un+vn, vn+1= un−vn with u0=0 and v0=1.

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])

⎡
⎢
⎢
⎢
⎢
⎣

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

⎤
⎥
⎥
⎥
⎥
⎦