Gosper's algorithm: Difference between revisions

Revision as of 05:28, 16 May 2013

Revision as of 12:00, 5 May 2014

Line 5:

Step 1: Find a polynomial p such that, writing ''b''(''n'') = ''a''(''n'')/''p''(''n''), the ratio ''b''(''n'')/''b''(''n'' − 1) has the form ''q''(''n'')/''r''(''n'') where ''q'' and ''r'' are polynomials and no ''q''(''n'') has a nontrivial factor with ''r''(''n'' + ''j'') for ''j'' = 0, 1, 2, ... . (This is always possible, whether or not the series is summable in closed form.)

Step 2: Find a polynomial ''ƒƒ'' such that ''S''(''n'') = ''q''(''n'' + 1)/''p''(''n'') ''ƒƒ''(''n'') ''a''(''n''). If the series is summable in closed form then clearly a rational function ''ƒƒ'' with this property exists; in fact it must always be a polynomial, and an upper bound on its degree can be found. Determining ''ƒƒ'' (or finding that there is no such ''ƒƒ'') is then a matter of solving a system of linear equations.

==Relationship to Wilf–Zeilberger pairs==