A telescoping method for double summations

We present a method to prove hypergeometric double summation identities. Given a hypergeometric term F(n, i, j), we aim to find a difference operator L = a(0)(n)N-0 + a(1)(n)N-1 + (...) + ar(n)N-r and rational functions R-1 (n, i, j), R-2(n, i, j) such that LF = Delta (R1F) + Delta(j)(R2F). Based on simple divisibility considerations, we show that the denominators of R-1 and R-2 must possess certain factors which can be computed from F(n, i, j). Using these factors as estimates, we may find the numerators of R-1 and R-2 by guessing the upperbounds of the degrees and solving systems of linear equations. Our method is valid for the Andrews-Paule identity, Carlitz's identities, the Apery-Schmidt-Strehl identity, the Graham-Knuth-Patashnik identity, and the Petkovsek-Wilf-Zeilberger identity. (c) 2005 Elsevier B.V. All rights reserved.