AN IMPLEMENTATION OF ZEILBERGER'S FAST ALGORITHM

by PETER PAULE, MARKUS SCHORN and AXEL RIESE

Getting Started

First we load the package (make sure that you are in the right directory!):

<< RISC`fastZeil`

Fast Zeilberger Package version 3.61
written by Peter Paule, Markus Schorn, and Axel Riese
Copyright 1995-2009, Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

Next, we test if it works:

Gosper[k^2, k]

Input Syntax

The interfaces to Gosper's and Zeilberger's algorithm are:

? Zb

? Gosper

As function we accept a product of factorials, binomials, pochhammers, rational-function terms and exponential expressions in the summation and recursion variable. All these factors can be raised to an integer power.

The arguments of a factorial or a binomial must be integer-linear in the summation variable and the recursion variable. That means they are of the form:

 		Integer * RecVar + Integer * SumVar + Constant.

The base of an exponential expression must be free of the summation and recursion variable, the exponent must be integer-linear in both of these variables.

The program will report violations of any of these restrictions.

Viewing the Output

In the output abbreviations like SUM, F and R appear. You can use the command Show to reveal their content, for instance show[SUM].

Zb[Binomial[n,k],k,n,1]

?F

show[F]

?R

show[R]

Another example:

Zb[Binomial[n,k],{k,0,n},n,1]

?SUM

show[SUM]

Computer Generated Proofs

After the execution of Gosper's or Zeilberger's algorithm you can obtain a computer proof by typing the following:

Prove[]

Some Examples

We compute a closed form for the sum of the squares:

Gosper[k^2, {k,0,n}]

We can also find the anti-difference of a square:

Gosper[k^2,k]

Summing Factorials fails, due to the fact, that there is no closed form for this sum:

Gosper[k!, {k,0,n}]

We can find a Gosper-summable function by attaching a polynomial factor:

Gosper[k!, {k,0,n}, 1]

We finish with two examples for the usage of Zeilberger's algorithm:

Zb[Binomial[n,k] x^k y^(n-k), k, n, 1]

show[F]

show[R]

Zb[Binomial[n,k] x^k y^(n-k), {k,0,n}, n, 1]

Prove[]