rec -- the domain of recurrence
equations
Introductionrec(eq, y(n)) represents a recurrence
equation for the sequence y(n).
Call(s)rec(eq, y(n) <, cond>)
Parameterseq |
- | 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 |
Returnsan object of type rec.
Related
Functions
Detailsrec(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.
Example
1The 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.
Example
2In 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).
Example
3In 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}
Example
4We 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.
Example
5For 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}
Example
6The 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 |
|
/
Example
7The 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}
Backgroundsolve 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).