[PURRS-devel] base case assumptions

[Roberto Bagnara]

Shailesh Humbad wrote:
 > I am having a problem with the online version of PURRS.  I tried it
 > on a recurrence relation derived from an algorithm I'm working on, and
 > the resulting formula is off by one for even n.  I believe it may be
 > something to do with our assumptions for the base cases and starting
 > index.  Is that something that would affect the results?
 >
 > INPUT:
 > x(n) = x(n-2) + 2*n - 5  for n > 2
 > x(n) = 0 for n <= 2
 >
 > OUTPUT:
 > Exact solution for x(n) = -5+x(-2+n)+2*n
 > x(n) = 1/2*n^2+3/2*mod(n,2)+x(mod(n,2))-1/2*mod(n,2)^2-3/2*n
 >
 > RESULTS:
 > (n, x(n) Recurrence, x(n) PURRS)
 > (2, 0, -1)
 > (3, 1, 1)
 > (4, 3, 2)
 > (5, 6, 6)
 > (6, 10, 9)
 > (7, 15, 15)
 > (8, 21, 20)
 > (9, 28, 28)
 > (10, 36, 35)
 >
 > Note that the PURRS result is one less when n is even.  However, the
 > formula works when the base cases are x(0) = 1 and x(1) = 0.  In the
 > results shown above, my assumption is that both are equal to zero.

Dear Shailesh,

we have done significant progress in the development of PURRS, and
this is also reflected in the on-line demo.  You should now be able to
use the demo the way you wanted.  You can either:

- specify the right-hand side of the recurrence;
- specify the right-hand side of the recurrence
   _and_ any set of initial conditions and special cases.

In the first case you will obtain the symbolic solution of the
recurrence containing the initial conditions x(i), ..., x(i+k-1)
(where `i' is the first index for which the recurrence is well-defined
and `k' is the order of the recurrence).

In the second case you obtain the solution of the recurrence with the
specified initial conditions and special cases.

For instance, in the case of your example

     x(n) = x(n-2) + 2*n - 5

you can specify the set of initial conditions (notice that in this case
the recurrence is of the second order and thus PURRS requires at least
2 initial conditions) as, e.g.,

     x(0) = 0; x(1) = 0; x(2) = 0

obtaining the solution

     x(n) = 1+1/2*n^2-3/2*n
     for each n >= 1

(x(0) = 0 is considered as a special case).
Standard disclaimer: all this is work in progress, so you could
observe something unexpected results: please do not hesitate to
contact us if you do.  Thanks again for your feedback.
All the best

   the PURRS team

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it