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) = a_{1} x(n-1) + ... + a_{k} x(n-k)
+ p(n).
The coefficients a_{j} are rational numbers.
If a_{k} 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
y^{n} = a_{1} y^{n-1} + ... + a_{k}.
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
a_{1} may be parametric as well.
Examples
- 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.
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.
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.