Mailing Lists


Some Details About the Parma Recurrence Relation Solver

Here are some details about what PURRS does, the types of recurrences it can handle, how it checks the correctness of the solutions found, and how it communicates with its clients.

What PURRS Can Do

The main service provided by PURRS is confining the solution of recurrence relations. More precisely, PURRS attempts to find a closed formula for the solution of a recurrence x(n), and to simplify it if it is possible. By closed formula we mean a formula containing a number of `+' or `-' signs that is independent of the main variable n. If PURRS fails to find such a closed formula, it will express the solution, whenever possible, in terms of sums and/or products.

A closed formula (or its generalization involving symbolic sums and products) is guaranteed to exist only in rather special circumstances (described in more detail below), and in general PURRS will only find upper and lower bounds for the solution of the recurrence. In other words, PURRS will give two functions l(n) and u(n) such that l(n) ≤ x(n) ≤ u(n) for all positive integers n.

Types of Recurrences PURRS Can Handle

Linear Recurrences of Finite Order with Constant Coefficients

These are recurrences like x(n) = 2 x(n-1) + a or x(n) = 2 x(n-1) - x(n-2), or, more generally x(n) = a1 x(n-1) + ... + ak x(n-k) + p(n). The coefficients aj are rational numbers. If ak is not zero, we say that the recurrence has order k. The function p(n) need not be there. If present, it is called non-homogeneous part of the recurrence. A typical example of this class is the recurrence satisfied by the Fibonacci numbers.

It is well known that it is possible to give a complete solution of the recurrence above as a function of its k initial values (that is, x(0), ... , x(k-1)) and of the solutions of the characteristic equation yn = a1 yn-1 + ... + ak. If the characteristic equation can be solved (for example, if k does not exceed 4), and if the function p(n) is a sum of products of polynomials and exponentials, PURRS computes the solution of the recurrence, giving an exact, closed formula.

The initial values are x(0), ..., x(k-1) and they appear in the solution of the recurrence. Notice that symbolic parameters are allowed in the function p(n). If the order of the recurrence is 1, the coefficient a1 may be parametric as well.


  • The recurrence x(n) = 2*x(n-1) + 1 appears in the solution of the so-called Hanoi-tower puzzle. PURRS gives the solution as x(n) = -1 + 2^n + 2^n*x(0), with an explicit reference to the initial value x(0). Future releases will allow users to specify this value, or to give a different initial value, like x(2), if desired.
  • PURRS will also solve a recurrence like x(n) = a*x(n-1) + 1, where the user has specified a parameter a. In this case, the solution is x(n) = a^n*x(0) - a^n - (-1+a)^(-1) + a*a^n*(-1+a)^(-1), and it obviously depends on the parameter, as well as on the initial condition as in the previous example.
  • In the case of a recurrence of order 2 or more, for the time being parameters are allowed only in the non-homogeneous part. For example, the solution of the recurrence x(n) = 2*x(n-1)-x(n-2)+a is x(n) = x(1)*n - 1/2*a*n + 1/2*a*n^2 + (1-n)*x(0). Notice that the solution depends on two initial values and on the user-specified parameter.

Linear Recurrences of Order 1 with Variable Coefficients

These are recurrences of the form x(n) = a(n) * x(n-1) + p(n). A typical example of this class is the recurrence satisfied by the factorial function. It is more difficult to characterize completely the set of such recurrences that have a solution in closed form: PURRS will attempt to express the solution using polynomials, exponentials and factorials, or a suitable combination of the same functions.

For this kind of recurrences there is only one initial value: usually it is x(0), but, depending on the domain of the functions a and p, PURRS computes automatically another starting point if 0 is not appropriate.

Infinite Order Recurrences

These are recurrences of the form x(n) = sum(k, 0, n-1, a(n)*x(k)) + b(n). Here x(n) depends on all the previous values, and not only a fixed number of them. PURRS is able to transform and solve a class of such recurrences.

Generalized (Divide-Et-Impera) Recurrences

These are recurrences of the form x(n) = a * x(n/b) + p(n), where a is positive, b > 1 and p(n) is a function whose domain is the set of positive integers, and the value n/b is always understood as its integer part. A typical example of this class is the recurrence satisfied by the worst-case complexity of the merge-sort algorithm. Exact solutions may not exist, even in the simplest cases: therefore PURRS computes upper and lower bounds for the solution, if the function p(n) is non negative and non decreasing.

For reasons of consistency, the initial values of these recurrences start at 1, and are x(1), ..., x(b-1).

Please notice that in many interesting cases, PURRS gives explicit numerical inequalities, and not just upper bounds with hidden multiplicative factors as in the results containing the O notation.

It is quite important to notice that the case of generalized recurrences is much more complex than those considered above: the reasons depend on both initial values and the fact that, except for extremely rare cases, the solutions contain inequalities. We now give a detailed description of these issues, splitting the problem of finding upper and lower bounds for the solution in two: we first deal with the dependence on the initial conditions, and then with the non-homogeneous part.

Dependence of the solution on the initial values

The solution always contains only one initial value, as the reader can easily check studying the recurrence x(n) = x(n/3). Given our convention that the initial values are x(1) and x(2), one can compute successively x(3) = x(1), x(4) = x(1), x(5) = x(1), x(6) = x(2), x(7) = x(2), x(8) = x(2), x(9) = x(3) = x(1), ...
The precise dependence on the initial conditions has a rather ugly shape: assume that x(n) = a * x(n/b), where a is positive and b ≥ 2 is an integer. Define q = q(n,b) = floor(log(n)/log(b)) where floor(t) is the largest integer that does not exceed the real number t, and log denotes the natural logarithm (though, in this particular case, the base is immaterial). The exact solution of the given recurrence is therefore x(n) = a^q * x( floor(n/b^q) ), where the argument of the x function on the right belongs to the set { 1, 2, ..., b-1 }. For the time being, PURRS gives an answer that, strictly speaking, is correct only if the initial values are non negative, and it is precisely

  • a^((log(n)/log(b))*x(floor(n/b^q))/a ≤ x(n) ≤ a^((log(n)/log(b))*x(floor(n/b^q)) if a > 1;
  • x(n) = x(floor(n/b^q)) if a = 1;
  • a^((log(n)/log(b))*x(floor(n/b^q)) ≤ x(n) ≤ a^((log(n)/log(b))*x(floor(n/b^q))/a if 0 < a < 1.
For those initial values that are negative, the user should exchange upper and lower bound.
Notice that if b = 2 there is only one possible initial value, namely x(1): PURRS knows this fact, and simplifies the output accordingly.

Dependence of the solution on the non-homogeneous part

Since, as already remarked, a solution in closed form may not exist, PURRS computes an upper and a lower bound for the value of x(n) for a fairly wide class of functions p(n), including polynomials, exponentials, logarithmic functions, the factorial function and sums of such functions. In these cases, the bounds computed contain explicit constants.

For the time being, PURRS does not allow parameters in the non-homogeneous part, but in most cases the user can obtain the solution just the same: this is best shown by means of an example. Assume you want to solve x(n) = 2*x(n/2) + a, which PURRS rejects as too complex. Ask PURRS to solve x(n) = 2*x(n/2) + 1, instead, and (assuming for simplicity that x(1) ≥ 0) you will obtain the inequalities
-1 + 1/2*x(1)*n + 1/2*n ≤ x(n) &le -1 + x(1)*n + n
All you have to do is to multiply the part of the answer that does not contain the initial condition by a, if a ≥ 0. If a < 0 then you also have to exchange the two between upper and lower bound. In other words, the full solution of the original, parametric recurrence is:

  • -a + 1/2*x(1)*n + 1/2*n*a ≤ x(n) &le -a + x(1)*n + n*a if a ≥ 0;
  • -a + 1/2*x(1)*n + n*a ≤ x(n) &le -a + x(1)*n + 1/2*n*a if a < 0.

Future releases of PURRS will deal with these issues automatically.

Multivariate recurrences

Automatic complexity analysis frequently leads to the synthesis of multivariate recurrence relations. While multivariate recurrences are really hard to solve in general, in many cases they can be converted into univariate recurrences so that all the techniques presented above become applicable. PURRS is often able to automatically perform such a rewriting step.

A very frequent and interesting case happens when the difference between the arguments of the unknown function x() is constant among all its occurrences in the multivariate recurrence relation. For instance, this happens for any recurrence relation having the form x(m,n) = f(x(m-1,n-1)), where the difference between the first and second argument of x() is always m-n. Such a recurrence can be rewritten as y(t) = f(y(t-1)), where y(t-k) = x(m-k,n-k), for all positive integer values of k.

Another interesting case, similar to the one above, is when the sum of the arguments of the unknown function x() is constant. For instance, multivariate recurrences of the form x(m,n) = f(x(m+1,n-1)) can be rewritten as y(t) = f(y(t-1)), where y(t-k) = x(m+k,n-k), for all positive integers k.

These rewriting techniques extend to recurrences involving more than two variables.

Verification of the Solutions

In the case when an exact solution has been successfully found, you can ask PURRS to check that the solution it computed actually satisfies the recurrence you typed. This is helpful in the fairly common case when the exact solution PURRS found is too complex or simply too long to carry out the computations by hand.

PURRS substitutes the suggested solution back into the original recurrence, and checks that both sides agree as a function of the integer variable n. Some special tricks have been built into PURRS in order to carry out this rather complex task as efficiently as possible.

When PURRS computes an upper or a lower bound for the solution, you can still ask for a proof of its correctness, and PURRS will handle the resulting inequalities.


  • Expression may include +, -, *, /, ^ (exponentiation), and parentheses. All constants must be integers.
  • Multiplication signs can not be omitted.
  • Any single lower-case letter different from e, n and x (e.g., a, b, c, z) is considered as a parameter. They can be used in the situations described above.
  • The function n! can be written either as such or as factorial(n). In the output it always appears in the second form.
  • Symbolic sums and products may be entered as sum(symbol,initial_value,final_value,summand) or prod(symbol,initial_value,final_value,summand) respectively, where summand is a function of the variable symbol. The expression initial_value must be a non negative integer, while final_value may depend on n.
  • PURRS has some proficiency at rewriting recurrences that are not given in its standard form: for example, if you give 2*x(n+1) as the RHS, it will solve x(n) = x(n-1)/2, instead.
  • For a positive integer k, the function mod(n,k) is defined to give the unique non negative integer r such that r < k and k divides n - r. In other words, mod(n,k) is the remainder that n leaves when divided by k.

[Page last updated on January 18, 2013, 09:58:05.]

© Roberto Bagnara

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