Summation of binomial coefficients using hypergeometric functions

ABSTRACT

An algorithm which finds the definite sum of many series involving binomial coefficients is presented. The method examines the ratio of two consecutive terms of the series in an attempt to express the sum as an ordinary hypergeometric function. A closed form for the infinite sum may be found by comparing the resulting function with known summation theorems. It may also be possible to identify ranges of the summation index for which summing to a finite upper limit is the same as summing to infinity.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: G. E. Andrews, "Applications of basic hypergeometric functions," SL4M Review 16 (1974), 441-484.
• 3: Luis Felipe Cabrera, Syntax oriented analysis of the run time performance of programs, 1981
• 4: G. P. Egorychev, Integral Representation and the Computation of Combinatorial Sums, American Mathematical Society (1984), 67-77.
• 5: R. W. Gosper, "Decision procedure for indefinite hypergeometric summation," Proe. Natl. Acad. Sei. USA 75 (1978), 40-42.
• 6: A. C. tlearn (ed.), REDUCE User's Manual, Version 3.1, Pub. CP78, Rand Corp., Santa Monica CA (1984).
• 7: Michael Karr, Summation in Finite Terms, Journal of the ACM (JACM), v.28 n.2, p.305-350, April 1981 [doi>10.1145/322248.322255]
• 8: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 9: J. C. Lafon, "Summation in finite terms," in B. Buchberser, G. E. Collins, and R. Loos (eds.), Computer Algebra: Symbolic and Algebraic Computation (2nd ed.), Spring;er-Verlag (1982), 71-77.
• 10: B. M. Minton, "Generalized hypergeometric function of unit argument," J. Math. Physic. 11 (1970), 1375- 1376.
• 11: R. Moenek, "On computing closed forms for summation," Proc. MACSYMA User's Conf. (1977), 225-236.
• 12: Paul Walton Purdom, Jr. , Cynthia A. Brown, The analysis of algorithms, Holt, Rinehart & Winston, Austin, TX, 1985
• 13: L. J. Slater, Generalized Hypergeometric Functions, Cambridge Univ. Press (1966).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems

          Nouns: REDUCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Iterative methods

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Automatic analysis of algorithms

General Terms:
Algorithms, Theory