Documentation |
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 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 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 non-constant 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 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)))
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 |
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.