×

Improvement of the degree setting in Gosper’s algorithm. (English) Zbl 0872.33001

This paper provides a useful detailed analysis of Gosper’s algorithm for indefinite hypergeometric summation; it will prove invaluable for readers wishing to understand and improve upon the algorithms employed to that end by familiar computing packages. The issue is, given polynomials \(\sigma\) and \(\tau\), to determine the sums \(\sum_{k=1}^n a_k\) for sequences \((a_k)\) given by recurrence relations \(a_k= (\sigma(k)/\tau(k)) a_{k-1}\). One of the crucial steps in Gosper’s algorithm is the determination of a degree bound for a possible polynomial solution of the key difference equation associated to the summation. The present analysis of that problem deals with that matter and, to do that, gives an instructive introduction to the principles underlying the algorithm. No doubt, readers other than the reviewer will be amused by the eccentric behaviour of Apery’s sequence in the present context.

MSC:

33-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to special functions
68W30 Symbolic computation and algebraic computation