Domain of recurrence equations
This functionality does not run in MATLAB.
rec(eq
, y(n
), <cond
>)
rec(eq, y(n))
creates an object of type rec
representing
a recurrence equation for the sequence 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 expressioneq
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
.
The main purpose of the 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. SeeExample 1, Example 4, and Example 5.
Currently only linear recurrences with coefficients that are
rational functions of 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 nonconstant 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
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))
solve(%)
Thus, the general solution of the recurrence equation is y(n) = C_{1} n 2^{n}, where C_{1} 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}))
Thus, the solution is 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}))
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)))
Here, C6
and C7
are arbitrary
constants.
For the following homogeneous third order recurrence with nonconstant coefficients, the system only finds the polynomial solutions:
solve(rec(n*y(n + 3) = (n + 3)*y(n), y(n)))
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)))
The following homogeneous second order recurrence with nonconstant
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)))

An equation or an arithmetical expression 

The unknown function: an identifier 

The index: an identifier 

A set of initial or boundary conditions 
Object of type rec
.
For homogeneous recurrences with constant coefficients, 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.
For first order homogeneous recurrences with nonconstant coefficients, 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.
For homogeneous recurrences of order at least two with nonconstant
coefficients, solve
finds
the complete space of all polynomial solutions.
Currently, inhomogeneous recurrences can only be solved if they have a polynomial solution. The previous remarks apply.
For parametric recurrences, the system may not find solutions that are valid only for special values of the parameters. Cf. Example 7.