[PURRS-devel] base case assumptions

[Shailesh Humbad]

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.

Thanks and Happy Holidays,
Shailesh