Mailing Lists


PURRS: The Parma University's Recurrence Relation Solver

Welcome to the home page of the Parma University's Recurrence Relation Solver, Parma Recurrence Relation Solver for short, PURRS for a very short. PURRS is a C++ library for the (possibly approximate) solution of recurrence relations. To be more precise, the PURRS already solves or approximates:

In the future, it will also solve systems of linear recurrence relations with constant coefficients. More details are available on the capabilities of the system.


Oct 28, 2004 Andrea made it, at last!
Andrea Pescetti got a Laurea degree in Mathematics with full marks and honors with a dissertation on his implementation of the Zeilberger algorithm (advisers Roberto Bagnara and Alessandro Zaccagnini). The thesis defense was really good (which is kind of strange, since the rehearsal one hour before the real show was deadly boring ;-)
Congratulations, Dottor Pescetti!
Aug 18, 2003 New paper available
The Automatic Solution of Recurrence Relations. I. Linear Recurrences of Finite Order with Constant Coefficients: this is the first in a series devoted to the presentation of all the mathematics behind the PURRS project. This paper describes algorithmic techniques for the efficient solution of a wide class of linear recurrences of finite order with constant coefficients. The presentation is thorough and reasonably self-contained, covering topics such as the automatic solution of polynomial equations and efficient, exact symbolic summation of some special functions.
For older news items, see the complete news archive.

Try PURRS online!

Here you can try a prototype of the solver. It showcases just the basic functionalities of PURRS (namely, you cannot solve multivariate recurrences through this web interface), but it may be instructive to play with it.

Recurrence relation
The expressions you can enter as the right hand side of the recurrence may contain the special symbol n (the index of the recurrence), and the special functional symbol x(). The argument of the functional symbol may be a non negative integer, an expression of the form n-k where k is a (possibly negative) integer, or of the form n/k, where k > 1 is an integer. The expression may also include operators +, -, *, /, ^ (exponentiation), parentheses, the functions log, exp and factorial(n); the latter may also be written n!. Any single lower-case letter different from e, n and x (e.g., a, b, c, z) will be considered as a parameter. Parameters are allowed to occur in the non homogeneous part of the recurrence. All numeric constants must be integers. A more detailed and precise description of what you can type and expect is available.
Beware: log(n) denotes the natural logarithm of n; if a base 2 logarithm is what you want, then you can write log(n)/log(2).

Examples of valid expressions are: 2*x(n-1)+a, 2*x(n-1)-x(n-2), n*x(n-1)+n, 3*x(n/2)+n*log(n), 3*x(n-1)^2, and 2*sum(k,0,n-1,x(k))+2*n.

x(n) =
Initial conditions:
Verify the solution
This is computed on an AMD processor running GNU/Linux.
Initial conditions
If you want you can specify initial conditions for the recurrence. The single initial condition must be of the form x(i)=k, for i a positive integer and k a number (not a floating point) or a symbolic expression containing the parameters a, b,..., z different from n, x and e. If the initial conditions are more than one, they must be separated by a semicolon. Please note: this a very experimental feature and may give unexpected results.

Examples of valid expressions are:
x(0)=a; x(1)=b

You can test some individual components of PURRS in the demos page.

[Page last updated on December 03, 2012, 08:27:55.]

© Roberto Bagnara

Home | Documentation | Download | Credits | Mailing Lists | Links