TOPICS
Search

Binomial Sums

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The important binomial theorem states that

sum_(k=0)^n(n; k)r^k=(1+r)^n.
(1)

Consider sums of powers of binomial coefficients

a_n^((r))=sum_(k=0)^(n)(n; k)^r
(2)
=_rF_(r-1)(-n,...,-n_()_(r);1,...,1_()_(r-1);(-1)^(r+1)),
(3)

where _pF_q(a_1,...,a_p;b_1,...,b_q;z) 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 r=1, the closed-form solution is given by

a_n^((1))=2^n,
(4)

i.e., the powers of two. a_n^((1)) obeys the recurrence relation

a_(n+1)^((1))-2a_n^((1))=0.
(5)

For r=2, the closed-form solution is given by

a_n^((2))=(2n; n).
(6)

i.e., the central binomial coefficients. a_n^((2)) obeys the recurrence relation

(n+1)a_(n+1)^((2))-(4n+2)a_n^((2))=0.
(7)

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

(n+1)^2a_(n+1)^((3))-(7n^2+7n+2)a_n^((3))-8n^2a_(n-1)^((3))=0
(8)

(Riordan 1980, p. 193; Barrucand 1975; Cusick 1989; Jin and Dickinson 2000), so a_n^((3)) are sometimes called Franel numbers. The sequence for a_n^((3)) 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 a_n^((4)),

(n+1)^3a_(n+1)^((4))-2(2n+1)(3n^2+3n+1)a_n^((4)) -4n(4n+1)(4n-1)a_(n-1)^((4))=0
(9)

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

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

32(n+1)^4(55n^2+253n+292)a_n^((5))+(19415n^6+205799n^5+900543n^4+2082073n^3+2682770n^2+1827064n+514048)a_(n+1)^((5))+(1155n^6+14553n^5+75498n^4+205949n^3+310827n^2+245586n+79320)a_(n+2)^((5))+(n+3)^4(55n^2+143n+94)a_(n+3)^((5))=0.
(10)

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

rOEISa_n^((r))
1A0000791, 2, 4, 8, 16, 32, 64, ...
2A0009841, 2, 6, 20, 70, 252, 924, ...
3A0001721, 2, 10, 56, 346, 2252, ...
4A0052601, 2, 18, 164, 1810, 21252, ...
5A0052611, 2, 34, 488, 9826, 206252, ...

The corresponding alternating series is

b_n^((r))=sum_(k=0)^(n)(-1)^k(n; k)^r
(11)
=_rF_(r-1)(-n,...,-n_()_(r);1,...,1_()_(r-1);(-1)^(r+1)),
(12)

The first few values are

b_n^((1))=0
(13)
b_n^((2))=(2^nsqrt(pi))/(Gamma(1/2-1/2n)Gamma(1+1/2n)),
(14)
=2^nP_n(0)
(15)
={0 for n=2k-1; (-1)^k(2k; k) for n=2k
(16)
b_n^((3))=(2^nsqrt(pi)Gamma(1+3/2n))/(n!Gamma(1/2(1-n))Gamma(1+1/2n)^2)
(17)
={0 for n=2k-1; ((-1)^k(3k)!)/((k!)^3) for n=2k,
(18)

where Gamma(z) is the gamma function, P_n(x) is a Legendre polynomial, and the odd terms of b_3(n) are given by de Bruijn's s(3,n) with alternating signs.

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

nb_n^((2))+4(n-1)a_(n-2)^((2))=0 n^2b_n^((3))+3(9n^2-18n+8)b_(n-2)^((3))=0 (n-1)n^3(12n^2-63n+83)b_n^((4))+4(408n^6-3774n^5+13760n^4-25203n^3+24465n^2-11970n+2340)b_(n-2)^((4))+16(n-2)(n-3)^3(12n^2-15n+5)b_(n-4)^((4))=0.
(19)

Sums of the form sum_(k=0)^(n)(n; k)k^r (Boros and Moll 2004, pp. 14-15) are given by

sum_(k=0)^(n)(n; k)=2^n
(20)
sum_(k=0)^(n)k(n; k)=2^(n-1)n
(21)
sum_(k=0)^(n)k^2(n; k)=2^(n-2)n(n+1)
(22)
sum_(k=0)^(n)k^3(n; k)=2^(n-3)n^2(n+3)
(23)
sum_(k=0)^(n)k^4(n; k)=2^(n-4)n(n+1)(n^2+5n-2)
(24)
sum_(k=0)^(n)k^5(n; k)=2^(n-5)n^2(n^3+10n^2+15n-10),
(25)

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

de Bruijn (1981) has considered the sum

s(m,n)=sum_(k=0)^(2n)(-1)^(k+n)(2n; k)^m
(26)

for m,n>=1. This sum has closed form for m=1, 2, and 3,

s(1,n)=0
(27)
s(2,n)=((2n)!)/((n!)^2),
(28)

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

s(3,n)=((3n)!)/((n!)^3),
(29)

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

An interesting generalization of b_1(n) is given by

sum_(k=0)^n(-1)^k(n; k)(x-k)^n=n!
(30)

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

The infinite sum of inverse binomial coefficients has the analytic form

sum_(k=0)^(infty)1/((n; k))=_2F_1(1,1;-n;-1)
(31)
=-(n+1)int_0^1(dx)/((1-x)^(n+2)(x+1)),
(32)

where _2F_1(a,b;c;x) is a hypergeometric function. In fact, in general,

sum_(k=0)^infty1/((n; k)^p)=_(p+1)F_p(1,...,1_()_(p+1);-n,...,-n_()_(p);(-1)^p)
(33)

and

sum_(k=0)^infty((-1)^k)/((n; k)^p)=_(p+1)F_p(1,...,1_()_(p+1);-n,...,-n_()_(p);(-1)^(p+1)).
(34)

Another interesting sum is

sum_(k=0)^(n)(n!)/(k!)=eGamma(n+1,1)
(35)
=|_n!e_|,
(36)

where Gamma(a,x) is an incomplete gamma function and |_x_| is the floor function. The first few terms for n=1, 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

sum_(n=1)^(infty)1/((2n; n))=1/(27)(2pisqrt(3)+9)
(37)
sum_(n=1)^(infty)1/(n(2n; n))=1/9pisqrt(3)
(38)
sum_(n=1)^(infty)1/(n^2(2n; n))=1/3zeta(2)=1/(18)pi^2
(39)
sum_(n=1)^(infty)1/(n^3(2n; n))=1/(18)pisqrt(3)[psi_1(1/3)-psi_1(2/3)]-4/3zeta(3)
(40)
sum_(n=1)^(infty)1/(n^4(2n; n))=(17)/(36)zeta(4)=(17)/(3240)pi^4
(41)
sum_(n=1)^(infty)1/(n^5(2n; n))=1/(432)pisqrt(3)[psi_3(1/3)-psi_3(2/3)]-(19)/3zeta(5)+1/9zeta(3)pi^2
(42)
sum_(n=1)^(infty)1/(n^7(2n; n))=(11)/(311040)pisqrt(3)[psi_5(1/3)-psi_5(2/3)]-(493)/(24)zeta(7)+1/3zeta(5)pi^2+(17)/(1620)zeta(3)pi^4,
(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

sum_(n=1)^infty1/(n^k(2n; n))=1/2_(k+1)F_k(1,...,1_()_(k+1);3/2,2,...,2_()_(k-1);1/4)
(44)

for k>=1, where _mF_n(a_1,...,a_m;b_1,...,b_n;x) is a generalized hypergeometric function and psi_n(x) is the polygamma function and zeta(x) is the Riemann zeta function (Plouffe 1998).

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

sum_(n=1)^infty((-1)^(n-1))/(n2^n(2n; n))=1/3ln2.
(45)

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

sum_(n=1)^(infty)(18-9n)/((2n; n))=(2pi)/(sqrt(3))
(46)
sum_(n=0)^(infty)(50n-6)/((3n; n)2^n)=pi
(47)
sum_(n=1)^(infty)(-150n^2+230n-36)/((3n; n)2^n)=pi
(48)
sum_(n=1)^(infty)(575n^2-965n+273)/((3n; n)2^n)=-6ln2
(49)

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

sum_(n=1)^(infty)(n^k)/((2n; n))=1/2(-1)^(k+1)sum_(j=1)^(k+1)((-1)^jj!S(k+1,j))/(3^j)(2j; j)×[(2pi)/(3sqrt(3))+sum_(i=0)^(j-1)(3^i)/((2i+1)(2i; i))]
(50)
=p_k+q_kpi/(sqrt(3)),
(51)

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

sum_(n=1)^(infty)1/((2n; n))=1/3+2/9pi/(sqrt(3))
(52)
sum_(n=1)^(infty)n/((2n; n))=2/3+2/9pi/(sqrt(3))
(53)
sum_(n=1)^(infty)(n^2)/((2n; n))=4/3+(10)/(27)pi/(sqrt(3)),
(54)

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

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

sum_(n=1)^infty(n^k)/((3n; n)2^n)=r_k+s_kpi+t_kln2.
(55)

The first few of these are

sum_(n=1)^(infty)1/((3n; n)2^n)=2/(25)-6/(125)ln2+(11)/(250)pi
(56)
sum_(n=1)^(infty)n/((3n; n)2^n)=(81)/(625)-(18)/(3125)ln2+(79)/(3125)pi
(57)
sum_(n=1)^(infty)(n^2)/((3n; n)2^n)=(561)/(3125)+(42)/(15625)ln2+(673)/(31250)pi,
(58)

giving values for r_k as 2/25, 81/625, 561/3125, ..., for s_k as -6/125, -18/3125, 42/15625, ..., and for t_k as 11/250, 79/3125, 673/31250, ....

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

sum_(n=1)^infty1/(n^3(3n; n)2^n)
(59)

in terms of multidimensional polylogarithms.

Sums of the form

sum_(n=1)^infty((-1)^(n+1))/(n^k(2n; n))=1/2_(k+1)F_k(1,...,1_()_(k+1);3/2,2,...,2_()_(k-1);-1/4)
(60)

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

sum_(n=1)^(infty)((-1)^(n-1))/(n(2n; n))=2/5sqrt(5)csch^(-1)2=2/5sqrt(5)lnphi
(61)
sum_(n=1)^(infty)((-1)^(n-1))/(n^2(2n; n))=2(csch^(-1)2)^2=2(lnphi)^2
(62)
sum_(n=1)^(infty)((-1)^(n-1))/(n^3(2n; n))=2/5zeta(3).
(63)

Other general identities include

((a+b)^n)/a=sum_(k=0)^n(n; k)(a-kc)^(k-1)(b+kc)^(n-k)
(64)

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

sum_(n=0)^(infty)(2n+s; n)x^n=_2F_1(1/2(s+1),1/2(s+2);s+1,4x)
(65)
=(2^s)/((sqrt(1-4x)+1)^ssqrt(1-4x)),
(66)

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

For nonnegative integers n and r with r<=n+1,

sum_(k=0)^n((-1)^k)/(k+1)(n; k)[sum_(j=0)^(r-1)(-1)^j(n; j)(r-j)^(n-k)+sum_(j=0)^(n-r)(-1)^j(n; j)(n+1-r-j)^(n-k)]=n!.
(67)

Taking n=2r-1 gives

sum_(k=0)^n((-1)^k)/(k+1)(n; k)sum_(j=0)^(r-1)(n; j)(r-j)^(n-k)=1/2n!.
(68)

Other identities are

sum_(k=0)^n(n+k; k)[x^(n+1)(1-x)^k+(1-x)^(n+1)x^k]=1
(69)

(Gosper 1972) and

sum_(i)(n_i; 2)+sum_(i>j)n_in_j=(n; 2),
(70)

where

n=sum_(i)n_i.
(71)

The latter is the umbral analog of the multinomial theorem for n^2

((a+b+c)^2)/2=(a^2)/2+(b^2)/2+(c^2)/2+ab+ac+bc
(72)

using the lower-factorial polynomial (n)_2=n(n-1)/2, giving

(a+b+c; 2)=(a; 2)+(b; 2)+(c; 2)+ab+ac+bc.
(73)

The identity holds true not only for (n)_2 and n^2/2, but also for any quadratic polynomial of the form n(n+a)/2.

Sinyor et al. (2001) give the strange sum

sum_(l^'<=l)sum_(j^'<=j)1/(m-l^')(m+l^(')-j^('); 2l^(')-j^(')+1)(m-l^(')+j^(')-1; j^('))(m-l^('); 2(l-l^('))-(j-j^(')))(m-l^('); j-j^('))
(74)
=1/(2(m-l))(2m; 2l+1)(2l+1; j)
(75)
=1/(2l+1)(2m; 2l)(2l+1; j).
(76)

See also

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

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.

Referenced on Wolfram|Alpha

Binomial Sums

Cite this as:

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

Subject classifications