## `rec` -- the domain of recurrence equations

#### Introduction

`rec``(eq, y(n))` represents a recurrence equation for the sequence `y(n)`.

#### Call(s)

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

#### 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

#### Returns

an object of type `rec`.

#### Related Functions

`ode`, `solve`, `sum`

#### Details

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

- 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. Cf. the examples 1, 4, and 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.

#### Example 1

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.

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

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

                                          2
                                  {m n + n  - 1}

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

                                       n          n
                               {C6 (-1)  + C7 (-2) }

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

                                      {n C9}

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

                   /               {     /  1   \n       /    1   \n }
          piecewise| {0} if a = 0, { C11 | ---- |  + C10 | - ---- |  }
                   |               {     |  1/2 |        |    1/2 |  }
                   \               {     \ a    /        \   a    /  }

                        \
              if a <> 0 |
                        |
                        /

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

                                        {0}

#### Background

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

#### Changes

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

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000