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.
Find un, given that un+1=2un+n 3n and u0=3.
seqsolve(2x+n*3^n,[x,n],3) |
Find un, given that un+1=un+un−1, u0=0 and
u1=1.
seqsolve(x+y,[x,y,n],[0,1]) |
|
| 5 | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | −4 | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | | √ | | −5 | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | +5 | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | +4 | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | | √ | | −5 | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | |
|
|
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]) |
Find un, given that un+1=2un+n and u0=3.
rsolve(u(n+1)=2*u(n)+n,u(n),u(0)=3) |
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+ | | · 2n−1,−n+ | | · 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) |
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 | √ | | +60 | ⎞
⎟
⎠ | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | +60 | √ | | −140 |
|
|
40 | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | +20 | √ | | −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) |
|
| ⎡
⎢
⎢
⎢
⎢
⎢
⎣ | − | | | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | + | | | √ | | | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | ⎤
⎥
⎥
⎥
⎥
⎥
⎦ |
| | | | | | | | | | |
|
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 | ⎞
⎟
⎠ | ⎛
⎜
⎝ | − | √ | | ⎞
⎟
⎠ | | + | | | ⎛
⎜
⎝ | √ | | +1 | ⎞
⎟
⎠ | · 2 | |
| |
| ⎤
⎥
⎥
⎥
⎥
⎦ |
|
| | | | | | | | | | |
|