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
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?
Dear Shailesh,
you are right: the online demo assumes that, for a recurrence of order k, the initial conditions are given for x(0), ..., x(k-1). We are working at a revision of our system (that currently is, remember, only a research prototype) that will allow to specify any set of initial conditions and special cases. We will also extend the online demo so as to make this facilities available through the web.
Thanks and Happy Holidays,
Thanks for your input. Have a great 2004,
Roberto Bagnara on behalf of the PURRS team
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
participants (2)
-
Roberto Bagnara -
Shailesh Humbad