[PURRS-devel] base case assumptions
Shailesh Humbad
humbads at alum.mit.edu
Fri Dec 26 09:16:05 CET 2003
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
More information about the PURRS-devel
mailing list