chapter 13

Zeilberger’s Algorithm

Pages 12

The aim is to find a difference equation satisfied by the sums T (a, n) with coefficients that are rational in n, i.e., to find an equation

β0(n)T (a, n) + β1(n)T (a, n + 1) + · · ·+ β(n)T (a, n + ) = 0. To do that we seek to sum the corresponding terms

β0(n)t(a, n, k) + β1(n)t(a, n + 1, k) + · · ·+ β(n)t(a, n + , k) by Gosper’s algorithm on the form ∆S(a, n, k), because with the terms, the sums S(a, n, k) must also vanish outside a finite interval. Hence, we have

∆S(a, n, k) = ∞∑

k=−∞ S(a, n, k + 1)−

S(a, n, k) = 0.