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