Recurrence Equations

This module is intended for solving recurrences (difference equations).

diofant.solvers.recurr.rsolve(f, *y, init={}, simplify=True)[source]

Solve recurrence equations.

The equations can involve objects of the form \(y(n + k)\), where \(k\) is a constant.

Parameters:

  • f (Expr, Equality or iterable of above) – The single recurrence equation or a system of recurrence equations.

  • *y (tuple) – Holds function applications \(y(n)\), wrt to which the recurrence equation(s) will be solved. If none given (empty tuple), this will be guessed from the provided equation(s).

  • init (dict, optional) – The initial/boundary conditions for the recurrence equations as mapping of the function application \(y(n_i)\) to its value. Default is empty dictionary.

  • simplify (bool, optional) – Enable simplification (default) on solutions.

Examples

>>> eq = (n - 1)*f(n + 2) - (n**2 + 3*n - 2)*f(n + 1) + 2*n*(n + 1)*f(n)

>>> rsolve(eq)
[{f: Lambda(n, 2**n*C0 + C1*factorial(n))}]
>>> rsolve(eq, init={f(0): 0, f(1): 3})
[{f: Lambda(n, 3*2**n - 3*factorial(n))}]

Notes

Currently, the function can handle linear recurrences with polynomial coefficients and hypergeometric inhomogeneous part.

See also

diofant.solvers.ode.dsolve

solving differential equations

diofant.solvers.solvers.solve

solving algebraic equations

diofant.solvers.recurr.rsolve_hyper(coeffs, f, n)[source]

Find hypergeometric solutions for linear recurrence.

Given linear recurrence operator \(\operatorname{L}\) of order \(k\) with polynomial coefficients and inhomogeneous equation \(\operatorname{L} y = f\) we seek for all hypergeometric solutions over field \(K\) of characteristic zero.

The inhomogeneous part can be either hypergeometric or a sum of a fixed number of pairwise dissimilar hypergeometric terms.

Notes

The algorithm performs three basic steps:

  1. Group together similar hypergeometric terms in the inhomogeneous part of \(\operatorname{L} y = f\), and find particular solution using Abramov’s algorithm.

  2. Compute generating set of \(\operatorname{L}\) and find basis in it, so that all solutions are linearly independent.

  3. Form final solution with the number of arbitrary constants equal to dimension of basis of \(\operatorname{L}\).

The output of this procedure is a linear combination of fixed number of hypergeometric terms. However the underlying method can generate larger class of solutions - D’Alembertian terms.

This method not only computes the kernel of the inhomogeneous equation, but also reduces in to a basis so that solutions generated by this procedure are linearly independent.

Examples

>>> rsolve_hyper([-1, 1], 1 + n, n)
(C0 + n*(n + 1)/2, [C0])

References

diofant.solvers.recurr.rsolve_poly(coeffs, f, n)[source]

Find polynomial solutions for linear recurrence.

Given linear recurrence operator \(\operatorname{L}\) of order \(k\) with polynomial coefficients and inhomogeneous equation \(\operatorname{L} y = f\), where \(f\) is a polynomial, we seek for all polynomial solutions over field \(K\) of characteristic zero.

Notes

The algorithm performs two basic steps:

  1. Compute degree \(N\) of the general polynomial solution.

  2. Find all polynomials of degree \(N\) or less of \(\operatorname{L} y = f\).

There are two methods for computing the polynomial solutions. If the degree bound is relatively small, i.e. it’s smaller than or equal to the order of the recurrence, then naive method of undetermined coefficients is being used. This gives system of algebraic equations with \(N+1\) unknowns.

In the other case, the algorithm performs transformation of the initial equation to an equivalent one, for which the system of algebraic equations has only \(r\) indeterminates. This method is quite sophisticated (in comparison with the naive one) and was invented together by Abramov, Bronstein and Petkovšek.

It is possible to generalize the algorithm implemented here to the case of linear q-difference and differential equations.

Examples

Lets say that we would like to compute \(m\)-th Bernoulli polynomial up to a constant, using \(b(n+1) - b(n) = m n^{m-1}\) recurrence:

>>> rsolve_poly([-1, 1], 4*n**3, n)
(C0 + n**4 - 2*n**3 + n**2, [C0])
>>> bernoulli(4, n)
n**4 - 2*n**3 + n**2 - 1/30

References

diofant.solvers.recurr.rsolve_ratio(coeffs, f, n)[source]

Find rational solutions for linear recurrence.

Given linear recurrence operator \(\operatorname{L}\) of order \(k\) with polynomial coefficients and inhomogeneous equation \(\operatorname{L} y = f\), where \(f\) is a polynomial, we seek for all rational solutions over field \(K\) of characteristic zero.

Notes

The algorithm performs two basic steps:

  1. Compute polynomial \(v(n)\) which can be used as universal denominator of any rational solution of equation \(\operatorname{L} y = f\).

  2. Construct new linear difference equation by substitution \(y(n) = u(n)/v(n)\) and solve it for \(u(n)\) finding all its polynomial solutions. Return None if none were found.

Algorithm implemented here is a revised version of the original Abramov’s algorithm, developed in 1989. The new approach is much simpler to implement and has better overall efficiency. This method can be easily adapted to q-difference equations case.

Besides finding rational solutions alone, this functions is an important part of the Hyper algorithm were it is used to find particular solution of inhomogeneous part of a recurrence.

Examples

>>> rsolve_ratio([-2*n**3 + n**2 + 2*n - 1, 2*n**3 + n**2 - 6*n,
...               -2*n**3 - 11*n**2 - 18*n - 9,
...               2*n**3 + 13*n**2 + 22*n + 8], 0, n)
(C2*(2*n - 3)/(2*(n**2 - 1)), [C2])

References

See also

rsolve_hyper