In the book "A = B" by Petkovesk, Wilf, and Zeilberger, [(downloadable here)](http://www.math.upenn.edu/~wilf/Downld.html), the authors provide several algorithmic methods for finding closed forms or recurrences for sums involving e.g. binomial coefficients. Even more exciting, their methods provide seemingly short certificates for the truth of these computer-verified claims. In particular, the WZ method prints a single rational function as such a certificate.


In more detail, here is the broad outline of the WZ method, where I directly quote from page 25 of "A = B":



> 
> 1. Suppose that you wish to prove an identity of the form $\sum\_k t(n, k) = rhs(n)$,
>  and let’s assume, for now, that for each n it is true that the summand $t(n, k)$
>  vanishes for all $k$ outside of some finite interval.
> 2. Divide through by the right hand side, so the identity that you wish to prove
>  now reads as $\sum\_k F (n, k) = 1$, where $F (n, k) = t(n, k)/rhs(n)$.
> 3. Let $R(n, k)$ be the rational function that the WZ method provides as the proof
>  of your identity (this is described in Chapter 7 of "A=B"). Define a
>  new function $G(n, k) = R(n, k)F (n, k).$
> 4. You will now observe that the equation
>  $$F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k)$$
>  is true. Sum that equation over all integers $k$, and note that the right side
>  telescopes to 0. The result is that
>  $$\sum\_k F (n + 1, k) = \sum\_k F (n, k),$$
>  hence we have shown that $\sum\_k F (n, k)$ is independent of $n$, i.e., is constant.
> 5. Verify that the constant is $1$ by checking that $F (0, k) = 1$.
> 
> 
> 


What I want to know is:



> 
> Are there known bounds on the length of these certificates $R(n, k)$, in terms of the length of the description of the combinatorial sum in question? If so, what are they?
> 
> 
> 



How long are the certificates produced by the Zeilberger and WZ methods for solving combinatorial sums (A=B)?
Already for the case of Gosper summation (single-variable), it is known that things can get exponentially larger than the input, because the 'answer' fundamentally depends on the *dispersion* of the input term. You will find much more comprehensive answers in the papers of [Sergei Abramov](http://www.ccas.ru/sabramov/publications.htm) as well as those of [Marko Petkovsek](http://www.fmf.uni-lj.si/~petkovsek/papers.html) (especially so in their joint papers!)


The *disperson* of a polynomial $p(x)$ is the largest integer $n$ such that $p(x)$ and $p(x+n)$ have a non-trivial gcd. A good understanding of how dispersion enters the picture can be gotten from the paper [Shiftless decomposition and polynomial-time rational summation](http://dx.doi.org/10.1145/860854.860887).


