-------- Original Message -------- Subject: Re: [PURRS-devel] base case assumptions Date: Fri, 23 Jan 2004 13:55:04 -0500 From: Shailesh Humbad humbads@alum.mit.edu To: Roberto Bagnara bagnara@cs.unipr.it References: 6.0.0.22.0.20031226022754.01ccf318@nyip.net 40116304.6060708@cs.unipr.it
Prof. Bagnara,
Wow, that is fantastic. I tried it online and it worked. Software that can do math always impresses me greatly.
When I use only two conditions, x(0) = 0 and x(1) = 0, I get what looks like old answer, which alternates by 1. When I use x(1)=0 and x(2)=0, I get the right answer. In my notes, I have x(0) as being undefined, as you say, a special case. So I think PURRS is working correctly, because this 2nd order recurrence's two initial conditions are actually x(1)=0 and x(2)=0.
For this recurrence, it was more important for me to know the complexity of the solution (i.e. polynomial or exponential) than the exact formula. I believe that in computer science this is usually the case. I don't know how PURRS does approximations, but if no other information could be calculated, then it might be useful if PURRS could determine just the order of the solution.
Just of interest, the solution factors to ((n-2)*(n-1))/2. This means it is simple enough to have been arrived at combinatorically, by studying the cases. I think software saves us time, but it makes us lazy ;)
Thank you for making this tool available online.
Shailesh
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@cs.unipr.it