Summation of functions over integers

[Lis Kłusownik]

Hello.

Is there will to implement routines that give closed forms for sums of particular functions over integers?

For example, how to find `sum(p(k) for k in range(n))` where `p(k)` is some polynomial with real coefficients? There is an algorithm in `O((deg p)^2)` which returns a polynomial `P(n)`, whose value at `n` is the desired sum.

Algorithm is based on discrete analogue to integral calculus. More information can be found in [1].

What do you think?

















[1] Graham, Ronald Lewis, 1935-
Concrete mathematics : a foundation for computer science
Ronald L. Graham, Donald E. Knuth, Oren Patashnik.
xiii,625 p. 24 cm.
Bibliography: p. 578
Includes index.
ISBN o-201-14236-8

[Leonid Kovalev]

I'm not familiar with the algorithm, but it looks like a good addition to eval_sum_symbolic method. Currently, if the sequence term is a sum it splits it in two and calls itself for each part. 

If the input was a polynomial, after some number of recursive calls (apparently, equal to the number of terms), it gets reduced to a monomial, for which the sum is evaluated with Faulhaber formula. 

So, implementing a direct approach that works with the entire polynomial would improve the performance. I imagine it would start with 

if f.is_polynomial(i):

and appear near the beginning of eval_sum_symbolic.