Symbolic summation (was: levin versus ratsum)

On 12/29/06, Michel Van den Bergh <michel.vandenbergh at uhasselt.be> wrote:
> Hi Richard,
>
> Thanks for chiming in. The point is that what seems to be missing
> in maxima is something like Closedform (-)! As a start we were
> discussing  just the easy case of summing rational functions.
> I think the current version of maxima does not even simplify
> a trivial telescoping sum like sum_k 1/k(k+1).

There is a closed_form function for sum simplification in maxima. It
uses Gosper and Zeilberger algorithms.

(%i1) load(closed_form)$
(%i2) sum(1/k/(k+1), k, 1, inf);
(%o2) sum(1/(k*(k+1)),k,1,inf)
(%i3) closed_form(%);
(%o3)  1

(%i6) sum(binomial(x,k)*binomial(y,n-k), k, 0, n);
(%o6) sum(binom(x,k)*binom(y,n-k),k,0,n)
(%i7) closed_form(%);
Is  x - n   positive, negative, or zero? pos;
Is  y - n   positive, negative, or zero? pos;
(%o7) ((y+x)*(y+x-1)!)/(n!*(y+x-n)!)
(%i8) factcomb(%);
(%o8) (y+x)!/(n!*(y+x-n)!)

> Yes as Miguel pointed out a couple of mails ago the answer is known and
> can be found in the handbook of Mathematical Functions if you want an
> aswer in terms of psi and polygamma functions (do these exist in maxima?).

Maxima knows how to numerically compute them

(%i10) load(bffac);
(%o10) C:/PROGRA~1/MAXIMA~1.0/share/maxima/5.10.0/share/numeric/bffac.mac
(%i11) bfpsi0(3, 10);  /* psi with 10 digits */
(%o11) 9.227843351b-1
(%i12) bfpsi(1, 1/3, 10); /* polygamma with 10 digits */
(%o12) 1.009559713b1

> But then one still needs to implement properties of these functions
> to simplify further. So it is perhaps better to use a special algorithm
> which has these simplifications built in (when they apply).
> This is what the paper by Ash and Catou does.
>
> But I don't really care as long as maxima would be able to evaluate
> something like sum(1/(3*n+1)^2+1/(3*n+2)^2,n,1) (I assume macsyma can do
> that?).

The closed form of sum(1/(3*n+1)^2 + 1/(3*n+2)^2, n, 0, inf) is
psi[1](1/3)/9 + psi[1](2/3)/9. Maxima does not compute it. Writing a
program which computes the closed form solution of sums of rational
function in terms of psi and polygamma should not be too hard. Since
maxima can compute these it would be interesting.

Andrej