TOPICS

# Binomial Sums

The important binomial theorem states that

 (1)

Consider sums of powers of binomial coefficients

 (2) (3)

where is a generalized hypergeometric function. When they exist, the recurrence equations that give solutions to these equations can be generated quickly using Zeilberger's algorithm.

For , the closed-form solution is given by

 (4)

i.e., the powers of two. obeys the recurrence relation

 (5)

For , the closed-form solution is given by

 (6)

i.e., the central binomial coefficients. obeys the recurrence relation

 (7)

Franel (1894, 1895) was the first to obtain recurrences for ,

 (8)

(Riordan 1980, p. 193; Barrucand 1975; Cusick 1989; Jin and Dickinson 2000), so are sometimes called Franel numbers. The sequence for cannot be expressed as a fixed number of hypergeometric terms (Petkovšek et al. 1996, p. 160), and therefore has no closed-form hypergeometric expression.

Franel (1894, 1895) was also the first to obtain the recurrence for ,

 (9)

(Riordan 1980, p. 193; Jin and Dickinson 2000).

Perlstadt (1987) found recurrences of length 4 for and 6.

 (10)

Schmidt and Yuan (1995) showed that the given recurrences for , 4, 5, and 6 are minimal, are the minimal lengths for are at least 3. The following table summarizes the first few values of for small .

 OEIS 1 A000079 1, 2, 4, 8, 16, 32, 64, ... 2 A000984 1, 2, 6, 20, 70, 252, 924, ... 3 A000172 1, 2, 10, 56, 346, 2252, ... 4 A005260 1, 2, 18, 164, 1810, 21252, ... 5 A005261 1, 2, 34, 488, 9826, 206252, ...

The corresponding alternating series is

 (11) (12)

The first few values are

 (13) (14) (15) (16) (17) (18)

where is the gamma function, is a Legendre polynomial, and the odd terms of are given by de Bruijn's with alternating signs.

Zeilberger's algorithm can be used to find recurrence equations for the s,

 (19)

Sums of the form (Boros and Moll 2004, pp. 14-15) are given by

 (20) (21) (22) (23) (24) (25)

where the triangle of the coefficients of the right-hand polynomials (ignoring the even/odd terms and ) are given by 1; 1, 3; 1, 5, ; 1, 10, 15, ; ... (OEIS A102573).

de Bruijn (1981) has considered the sum

 (26)

for . This sum has closed form for , 2, and 3,

 (27)
 (28)

the central binomial coefficient, giving 1, 2, 6, 20, 70, 252, 924, ... (OEIS A000984), and

 (29)

giving 1, 6, 90, 1680, 36450, 756756, ... (OEIS A006480; Aizenberg and Yuzhakov 1984). However, there is no similar formula for (de Bruijn 1981). The first few terms of are 1, 14, 786, 61340, 5562130, ... (OEIS A050983), and for are 1, 30, 5730, 1696800, 613591650, ... (OEIS A050984).

An interesting generalization of is given by

 (30)

for positive integer and all (Ruiz 1996). This identity is consequence of the fact the difference operator applied times to a polynomial of degree will result in times the leading coefficient of the polynomial. The above equation is just a special instance of this, with the general case obtained by replacing by any polynomial of degree with leading coefficient 1.

The infinite sum of inverse binomial coefficients has the analytic form

 (31) (32)

where is a hypergeometric function. In fact, in general,

 (33)

and

 (34)

Another interesting sum is

 (35) (36)

where is an incomplete gamma function and is the floor function. The first few terms for , 2, ... are 2, 5, 16, 65, 326, ... (OEIS A000522).

A fascinating series of identities involving inverse central binomial coefficients times small powers are given by

 (37) (38) (39) (40) (41) (42) (43)

(Comtet 1974, p. 89; Le Lionnais 1983, pp. 29, 30, 41, 36; Borwein et al. 1987, pp. 27-28), which follow from the beautiful formula

 (44)

for , where is a generalized hypergeometric function and is the polygamma function and is the Riemann zeta function (Plouffe 1998).

A nice sum due to B. Cloitre (pers. comm., Oct. 6, 2004) is given by

 (45)

Additional classes of binomial sums that can be done in closed form include

 (46) (47) (48) (49)

(Gosper 1974, Borwein and Borwein 1987; Borwein et al. 2004, pp. 20-25). Some of these follow from the general results

 (50) (51)

where is a Stirling number of the second kind and , are definite rational numbers (Borwein et al. 2004, pp. 23-25). The first few sums of the first form are

 (52) (53) (54)

giving values of as 2/3, 4/3, 10/3, 32/3, ..., and of as 2/9, 10/27, 74/81, ....

Similarly, the first few sums of the second form are given by

 (55)

The first few of these are

 (56) (57) (58)

giving values for as 2/25, 81/625, 561/3125, ..., for as , , 42/15625, ..., and for as 11/250, 79/3125, 673/31250, ....

Borwein (et al. 2004, pp. 27-28) conjecture closed-form solutions to sums of the form

 (59)

in terms of multidimensional polylogarithms.

Sums of the form

 (60)

can also be simplified (Plouffe 1998) to give the special cases

 (61) (62) (63)

Other general identities include

 (64)

(Prudnikov et al. 1986), which gives the binomial theorem as a special case with , and

 (65) (66)

where is a hypergeometric function (Abramowitz and Stegun 1972, p. 555; Graham et al. 1994, p. 203).

For nonnegative integers and with ,

 (67)

Taking gives

 (68)

Other identities are

 (69)

(Gosper 1972) and

 (70)

where

 (71)

The latter is the umbral analog of the multinomial theorem for

 (72)

using the lower-factorial polynomial , giving

 (73)

The identity holds true not only for and , but also for any quadratic polynomial of the form .

Sinyor et al. (2001) give the strange sum

 (74) (75) (76)

Apéry Number, Binomial, Binomial Coefficient, Central Binomial Coefficient, Christmas Stocking Theorem, Franel Number, Hypergeometric Identity, Hypergeometric Series, Idempotent Number, Jonah Formula Klee's Identity, Lucas Correspondence Theorem, Married Couples Problem, Morley's Formula, Nexus Number, Pascal's Formula, Schmidt's Problem, Stanley's Identity, Star of David Theorem, Strehl Identities, Székely Identity, Waring Formula, Worpitzky's Identity

## Explore with Wolfram|Alpha

More things to try:

## References

Abramowitz, M. and Stegun, I. A. (Eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, 1972.Aizenberg, I. A. and Yuzhakov, A. P. Integral Representations and Residues in Multidimensional Complex Analysis. Providence, RI: Amer. Math. Soc., p. 194, 1984.Almkvist, G.; Krattenthaler, C.; and Petersson, J. "Some New Formulas for Pi." Manuscript, 2001.Barrucand, P. "Problem 75-4: A Combinatorial Identity." SIAM Rev. 17, 168, 1975.Beukers, F. "Another Congruence for the Apéry Numbers." J. Number Th. 25, 201-210, 1987.Boros, G. and Moll, V. Irresistible Integrals: Symbolics, Analysis and Experiments in the Evaluation of Integrals. Cambridge, England: Cambridge University Press, 2004.Borwein, J.; Bailey, D.; and Girgensohn, R. "Evaluation of Binomial Series." §1.7 in Experimentation in Mathematics: Computational Paths to Discovery. Wellesley, MA: A K Peters, pp. 20-28, 2004.Borwein, J. M. and Borwein, P. B. Pi & the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, 1987.Borwein, J. M.; Broadhurst, D. J.; and Kamnitzer, J. "Central Binomial Sums, Multiple Clausen Values and Zeta Functions." Exp. Math. 10, 25-41, 2001.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, 1974.Cusick, T. W. "Recurrences for Sums of Powers of Binomial Coefficients." J. Combin. Th. Ser. A 52, 77-83, 1989.de Bruijn, N. G. Asymptotic Methods in Analysis. New York: Dover, 1981.Egorychev, G. P. Integral Representation and the Computation of Combinatorial Sums. Providence, RI: Amer. Math. Soc., 1984.Franel, J. "On a Question of Laisant." L'intermédiaire des mathématiciens 1, 45-47, 1894.Franel, J. "On a Question of J. Franel." L'intermédiaire des mathématiciens 2, 33-35, 1895.Gosper, R. W. Item 42 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 16, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/number.html#item42.Gosper, R. W. Unpublished research announcement. 1974.Graham, R. L.; Knuth, D. E.; and Patashnik, O. "Binomial Coefficients." Ch. 5 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 153-242, 1994.Jin, Y. and Dickinson, H. "Apéry Sequences and Legendre Transforms." J. Austral. Math. Soc. Ser. A 68, 349-356, 2000.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, 1983.MacMahon P. A. "The Sums of the Powers of the Binomial Coefficients." Quart. J. Math. 33, 274-288, 1902.McIntosh, R. J. "Recurrences for Alternating Sums of Powers of Binomial Coefficients." J. Combin. Th. A 63, 223-233, 1993.Perlstadt, M. A. "Some Recurrences for Sums of Powers of Binomial Coefficients." J. Number Th. 27, 304-309, 1987.Petkovšek, M.; Wilf, H. S.; and Zeilberger, D. A=B. Wellesley, MA: A K Peters, 1996. http://www.cis.upenn.edu/~wilf/AeqB.html.Plouffe, S. "The Art of Inspired Guessing." Aug. 7, 1998. http://www.lacim.uqam.ca/~plouffe/inspired.html.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, 1980.Ruiz, S. "An Algebraic Identity Leading to Wilson's Theorem." Math. Gaz. 80, 579-582, Nov. 1996.Schmidt, A. L. and Yuan, J. "On Recurrences for Sums of Powers of Binomial Coefficients." Tech. Rep., 1995.Shanks, E. B. "Iterated Sums of Powers of the Binomial Coefficients." Amer. Math. Monthly 58, 404-407, 1951.Sinyor, J.; Speevak, R.; and Tefera, A. "A New Combinatorial Identity." Int. J. Math. Math. Sci. 25, 361-363, 2001.Sloane, N. J. A. Sequences A000079/M1129, A000172/M1971, A000522/M1497, A000984/M1645, A005260/M2110, A005261/M2156, A006480/M4284, A050983, A050984, and A102573 in "The On-Line Encyclopedia of Integer Sequences."Strehl, V. "Binomial Identities--Combinatorial and Algorithmic Aspects. Trends in Discrete Mathematics." Disc. Math. 136, 309-346, 1994.

Binomial Sums

## Cite this as:

Weisstein, Eric W. "Binomial Sums." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BinomialSums.html