Documentation

# `rec`

Domain of recurrence equations

MuPAD® notebooks will be removed in a future release. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

## Syntax

```rec(`eq`, y(`n`), <`cond`>)
```

## Description

`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 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`.

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.

## Examples

### Example 1

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) = C1n 2n, where C1 is an arbitrary constant.

### Example 2

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).

### Example 3

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}))```
` `

### Example 4

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.

### Example 5

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)))`
` `

### Example 6

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)))`
` `

### Example 7

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)))`
` `

## Parameters

 `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

## Return Values

Object of type `rec`.

## Algorithms

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.