A probabilistic model for the degree of the cancellation polynomial in Gosper’s Algorithm

ABSTRACT: Gosper’s algorithm is a cornerstone of automated summation of hypergeometric series. Milenkovic and Compton in 2002 gave an analysis of the run time of Gosper’s algorithm applied to a random input. The main part of this was an asymptotic analysis of the random degree of the cancellation polynomial c(k) under various stipulated laws for the input. Their methods use probabilistic transform techniques. These results may also be obtained via probabilistic methods. Limit laws of the type proved by Milenkovic and Compton will be shown to follow from a general functional central limit theorem. Advantages to this approach include applicability to a more general class of input distributions and transparancy, in the sense that a non-quantitative limit theorem may be proved with no computation. A disadvantage to probabilistic methods is that one may typically derive only the leading term behavior. This is due to the inherent limit on precision in the Central Limit Theorem