rec
-- the domain of recurrence
equationsrec
(eq, y(n))
represents a recurrence
equation for the sequence y(n)
.
rec(eq, y(n) <, cond>)
eq |
- | an equation or an arithmetical expression |
y |
- | the unknown function: an identifier |
n |
- | the index: an identifier |
cond |
- | a set of initial or boundary conditions |
an object of type rec
.
rec
(eq, y(n))
creates an object of type
rec
representing a recurrence equation for
y(n)
.
The equation eq
must involve only shifts y(n +
i)
with integer values of i
; at least one such
expression must be present in eq
. An arithmetical expression eq
is
equivalent to the equation eq = 0
.
Initial or boundary conditions cond
must be specified
as sets of equations of the form {y(n0) = y0, y(n1) = y1,
...}
with arithmetical expressions
n0
, n1
, ...that must not contain the
identifier n
, and arithmetical
expressions y0
, y1
, ...that must not
contain the identifier y
.
rec
domain is to provide an
environment for overloading the function
solve
. For a recurrence
r
of type rec
, the call solve(r)
returns a set representing an affine subspace of the complete solution
space. Its only entry is an expression in n
that may
contain free parameters such as C1
, C2
etc.
Cf. the examples 1, 4, and
5.n
can be solved. solve
handles recurrences with
constant coefficients, it finds hypergeometric solutions of first order
recurrences, and polynomial solutions of higher order recurrences with
non-constant coefficients.solve
is not always
able to find the complete solution space. Cf. example 5. If solve
cannot find a solution, then the solve
call is returned symbolically.
For parametric recurrences, the output of solve
may be a conditionally defined
set of type piecewise
. Cf. example 6.The first command defines the homogeneous first order
recurrence equation y(n+1) = 2*(n+1)/n*y(n) for the sequence
y(n). It is solved by a call to the solve
function:
>> rec(y(n + 1) = 2*y(n)*(n + 1)/n, y(n))
/ 2 y(n) (n + 1) \ rec| y(n + 1) - --------------, y(n), {} | \ n /
>> solve(%)
n {n C1 2 }
Thus, the general solution of the recurrence equation is y(n) = C1*n*2^n, where C1 is an arbitrary constant.
In the next example, the homogeneous first order recurrence y(n+1) = 3*(n+1)*y(n) with the initial condition y(0)=1 is solved for the unknown sequence y(n):
>> solve(rec(y(n + 1) = 3*(n + 1)*y(n), y(n), {y(0) = 1}))
n {3 gamma(n + 1)}
Thus, the solution is y(n) = 3^n*gamma(n+1) = 3^n*n! for all integers n >=0 (gamma is the gamma function).
In the following example, the inhomogeneous second order
recurrence y(n+2) - 2*y(n+1) + y(n) = 2 is solved for the
unknown sequence y(n). The initial conditions
y(0)=-1 and y(1)=m with some parameter
m are taken into account by solve
:
>> solve(rec(y(n + 2) - 2*y(n + 1) + y(n) = 2, y(n), {y(0) = -1, y(1) = m}))
2 {m n + n - 1}
We compute the general solution of the homogeneous second order recurrence y(n+2) + 3*y(n+1) + 2*y(n) = 0:
>> solve(rec(y(n + 2) + 3*y(n + 1) + 2*y(n), y(n)))
n n {C6 (-1) + C7 (-2) }
Here, C6
and C7
are arbitrary
constants.
For the following homogeneous third order recurrence with non-constant coefficients, the system only finds the polynomial solutions:
>> solve(rec(n*y(n + 3) = (n + 3)*y(n), y(n)))
{n C9}
The following homogeneous second order recurrence with
constant coefficients involves a parameter a
. The solution
set depends on the value of this parameter, and solve
returns a piecewise
object:
>> solve(rec(a*y(n + 2) = y(n), y(n)))
/ { / 1 \n / 1 \n } piecewise| {0} if a = 0, { C11 | ---- | + C10 | - ---- | } | { | 1/2 | | 1/2 | } \ { \ a / \ a / } \ if a <> 0 | | /
The following homogeneous second order recurrence with
non-constant coefficients involves a parameter a
. Although
it has a polynomial solution for a=2, the system does not
recognize this:
>> solve(rec(n*y(n + 2) = (n + a)*y(n), y(n)))
{0}
solve
computes the roots of the
characteristic polynomial. If some of them cannot be given in explicit
form, i.e., only by means of RootOf
, then solve
does not return a solution.
Otherwise, the complete solution space is returned.solve
returns the complete solution space if the coefficients of the
recurrence can be factored into at most quadratic polynomials.
Otherwise, solve
does
not return a solution.solve
finds the complete space of all polynomial solutions.rec
now does some argument checking.solve
now returns a
set containing one expression, a symbolic solve
call, or a piecewise
object. The free
parameters, if any, are newly generated identifiers throughout, and no
longer symbolic initial values of the form y(n0)
.