Binomial Sums

Author

Eric W. Weisstein
September 27, 2007

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/BinomialSums.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/BinomialSums.html.

©2007 Wolfram Research, Inc. except for portions noted otherwise

Initialization

<<zb_alg.m

Binomial Theorem (∑_(k=0)^n)(({{n}, {k}}))(k^r)

Sum[r^k Binomial[n,k],{k,0,n}]

(∑_(k=1)^∞)((((-1))^(k-1))/(k (2^k) (({{2 k}, {k}}))))==((log(2))/3)

Sum[((((-1))^(k-1))/(k (2^k)Binomial[2k,k])),{k,∞}]//FullSimplify

(∑_(k=0)^n)(((({{n}, {k}})))^r)

General

Sum[(-1)^k Binomial[n,k]^r,{k,0,n}]

(Subtract@@@Table[{Sum[(-1)^k Binomial[n,k]^r,{k,0,n}],HypergeometricPFQ[Table[-n,{r}],Table[1,{r-1}],(-1)^(r+1)]},{r,5}]//FullSimplify)

FullSimplify[%,n>0]

r=-1

Sum[1/Binomial[n,k],{k,0,Infinity}]

r=(1/2)

Sum[Binomial[n,k]^(1/2),{k,0,n}]

r an integer

Table[Sum[Binomial[n,k]^r,{k,0,n}],{r,5}]//ColumnForm

r=1

Sum[Binomial[n,k],{k,0,n}]

RSolve[{a[n+1]-2a[n]==0,a[0]==1},a[n],n]

Table[(2^n),{n,10}]

r=2

FullSimplify[Sum[Binomial[n,k]^2,{k,0,n}]]

FullSimplify[%-Binomial[2n,n]]

FullSimplify[First[Zb[Binomial[n,k]^2,k,n,1][[1]]/.{F[k_,n_]:>a[n],Delta[__]:>0}]]

RSolve[{(n+1)a[n+1]-(4n+2)a[n]==0,a[0]==1},a[n],n]

FunctionExpand[%]

Table[(((4^n) Gamma[(1/2)+n])/((Sqrt[π]) Gamma[1+n])),{n,5}]

r=3

Sum[Binomial[n,k]^3,{k,0,n}]

Table[(∑_(k=0)^n)((Binomial[n,k])^3),{n,0,5}]

Simplify[First[Zb[Binomial[n,k]^3,k,n,2][[1]]/.{F[k_,n_]:>a[n],Delta[__]:>0}]/.n->n-1]

RSolve[{(n+1)^2 a[n+1]-(7n^2+7n+2)a[n]-8n^2 a[n-1]==0,a[0]==1,a[1]==2},a[n],n]

Solve[n^2 a[n]-(7(n-1)^2+7(n-1)+2)a[n-1]-8(n-1)^2 a[n-2]==0,a[n]]

Clear[a];
a[0]:=1
a[1]:=2
a[n_]:=((8 (((-1+n))^2) a[-2+n]+(2+7 (-1+n)+7 (((-1+n))^2)) a[-1+n])/(n^2))

Table[a[n],{n,0,5}]

r=4

Sum[Binomial[n,k]^4,{k,0,n}]

Table[(∑_(k=0)^n)((Binomial[n,k])^4),{n,0,10}]

Simplify[First[Zb[Binomial[n,k]^4,k,n,3][[1]]/.{F[k_,n_]:>a[n],Delta[__]:>0}]/.n->n-3]

Clear[a];
Simplify[Solve[n^3 a[n]-2(2(n-1)+1)(3(n-1)^2+3(n-1)+1)a[n-1]-4(n-1)(4(n-1)+1)(4(n-1)-1)a[n-2]==0,a[n]]]

Clear[a];
a[0]:=1
a[1]:=2
a[n_]:=(1/(n^3))(2 ((-30+94 n-96 (n^2)+32 (n^3)) a[-2+n]+(-1+5 n-9 (n^2)+6 (n^3)) a[-1+n]))

Table[a[n],{n,0,5}]

r=5

Sum[Binomial[n,k]^5,{k,0,n}]

Table[(∑_(k=0)^n)Binomial[n,k]^5,{n,0,10}]

Zb[Binomial[n,k]^5,k,n,2]

Simplify[First[Zb[Binomial[n,k]^5,k,n,3][[1]]/.{F[k_,n_]:>a[n],Delta[__]:>0}]]/.a[k_]:>Subsuperscript[a,k,"(5)"]//TraditionalForm

Simplify[First[Zb[Binomial[n,k]^5,k,n,4][[1]]/.{F[k_,n_]:>a[n],Delta[__]:>0}]]/.a[k_]:>Subsuperscript[a,k,"(5)"]//TraditionalForm

r=6

Sum[Binomial[n,k]^6,{k,0,n}]

Table[(∑_(k=0)^n)Binomial[n,k]^6,{n,0,10}]

Zb[Binomial[n,k]^6,k,n,2]

Simplify[First[Zb[Binomial[n,k]^6,k,n,3][[1]]/.{F[k_,n_]:>a[n],Delta[__]:>0}]]/.a[k_]:>Subsuperscript[a,k,"(5)"]//TraditionalForm

(∑_(k=0)^n)(({{n}, {k}}))(k^r)

Boros and Moll 2004, p.14

Sum[Binomial[n,k]k^r,{k,0,n}]

Table[{r,Factor[Sum[Binomial[n,k]k^r,{k,0,n}]]},{r,0,8}]//ColumnForm//TraditionalForm

Reverse[CoefficientList[#,n]]&/@Table[((2^(r-n))/(If[OddQ[r],n^2,n(n+1)]))Factor[Sum[Binomial[n,k]k^r,{k,0,n}]],{r,2,8}]

(∑_(k=0)^n)((n!)/(k!))

FullSimplify[Sum[n!/k!,{k,0,n}]]

Table[%,{n,5}]//FullSimplify

Table[Floor[n! E],{n,5}]

(∑_(k=0)^n)(((-1))^k) (((({{n}, {k}})))^r)

r an integer

Sum[(-1)^k Binomial[n,k]^r,{k,0,n}]

Table[Sum[Binomial[n,k]^r,{k,0,n}],{r,5},{n,0,10}]//ColumnForm

Table[HypergeometricPFQ[Table[-n,{r}],Table[1,{r-1}],(-1)^r],{r,5},{n,0,10}]//ColumnForm

Table[Sum[Binomial[n,k]^r,{k,0,n}],{r,5}]//FullSimplify//ColumnForm

Table[Sum[Binomial[n,k]^r(-1)^k,{k,0,n}],{r,5}]

Table[(((2^n) (Sqrt[π]))/(Gamma[(1/2)-(n/2)] Gamma[1+(n/2)])),{n,0,10}]

Table[(((2^n) (Sqrt[π]) Gamma[1+((3 n)/2)])/(Gamma[(1/2)-(n/2)] ((Gamma[1+(n/2)])^2) Gamma[1+n])),{n,0,10}]

Table[Sum[Binomial[n,k]^r(-1)^k,{k,0,n}],{r,5},{n,0,10}]//ColumnForm

r=1

Sum[(-1)^k Binomial[n,k],{k,0,n}]

Zb[Binomial[n,k](-1)^k,k,n,1][[1]]/.{F[k_,n_]:>b[n],Delta[__]:>0}/.b[k_]:>Subsuperscript[b,k,"(1)"]//TraditionalForm

r=2

FullSimplify[Sum[(-1)^k Binomial[n,k]^2,{k,0,n}],{n∈Integers,n>0}]

Table[Sum[(-1)^k Binomial[n,k]^2,{k,0,n}],{n,0,20}]

Table[If[EvenQ[n],0,k=(n+1)/2;(-1)^k Binomial[2k,k]],{n,0,20}]

Simplify[First[Zb[Binomial[n,k]^2(-1)^k,k,n,2][[1]]/.{F[k_,n_]:>b[n],Delta[__]:>0}]/.n->n-2]/.b[k_]:>Subsuperscript[b,k,"(2)"]//TraditionalForm

v4.2

<<DiscreteMath`RSolve`

RSolve[{a[n]==((4 (1-n) a[n-2])/n),a[0]==1,a[1]==0},a[n],n]

Table[2^n*LegendreP[n,0],{n,0,10}]

v5

RSolve[{a[n]==((4 (1-n) a[n-2])/n),a[1]==0,a[2]==-2},a[n],n]

r=3

Sum[(-1)^k Binomial[n,k]^3,{k,0,n}]

FullSimplify[Sum[(-1)^k Binomial[n,k]^3,{k,0,n}],n∈Integers&&n>0]

Table[%,{n,0,20}]

Table[If[OddQ[n],0,k=n/2;(-1)^k (3k)!/(k!)^3],{n,0,20}]

Simplify[First[Zb[Binomial[n,k]^3(-1)^k,k,n,2][[1]]/.{F[k_,n_]:>b[n],Delta[__]:>0}]/.n->n-2]/.b[k_]:>Subsuperscript[b,k,"(3)"]//TraditionalForm

v4.2

<<DiscreteMath`RSolve`

RSolve[{a[n]==((3 (8-18 n+9 (n^2)) a[-2+n])/(n^2)),a[0]==1,a[1]==0},a[n],n]

v5

RSolve[{a[n]==((3 (8-18 n+9 (n^2)) a[-2+n])/(n^2)),a[0]==1,a[1]==0},a[n],n]

r=4

Wrong

Sum[(-1)^k Binomial[n,k]^4,{k,0,n}]

Zb[Binomial[n,k]^4(-1)^k,k,n,2]

Zb[Binomial[n,k]^4(-1)^k,k,n,3]

Zb[Binomial[n,k]^4(-1)^k,k,n,4][[1]]/.{F[k_,n_]:>b[n],Delta[__]:>0}

Simplify[First[Zb[Binomial[n,k]^4(-1)^k,k,n,4][[1]]/.{F[k_,n_]:>b[n],Delta[__]:>0}]/.n->n-4]/.b[k_]:>Subsuperscript[b,k,"(4)"]//TraditionalForm

v4.2

<<DiscreteMath`RSolve`

RSolve[{-16 (((1+n))^3) (2+n) (137+81 n+12 (n^2)) b[n]-4 (62060+172598 n+194349 (n^2)+113357 (n^3)+36200 (n^4)+6018 (n^5)+408 (n^6)) b[2+n]-(3+n) (((4+n))^3) (23+33 n+12 (n^2)) b[4+n]==0,b[0]==1,b[1]==0},b[n],n]

v5

RSolve[{-16 (((1+n))^3) (2+n) (137+81 n+12 (n^2)) b[n]-4 (62060+172598 n+194349 (n^2)+113357 (n^3)+36200 (n^4)+6018 (n^5)+408 (n^6)) b[2+n]-(3+n) (((4+n))^3) (23+33 n+12 (n^2)) b[4+n]==0,b[0]==1,b[1]==0},b[n],n]

(∑_(n=1)^∞)(1/(((({{2 n}, {n}})))^k))

Sum[1/Binomial[n,k],{k,0,Infinity}]

Sum[1/Binomial[n,k]^2,{k,0,Infinity}]

Sum[1/Binomial[n,k]^3,{k,0,Infinity}]

Sum[(-1)^k/Binomial[n,k],{k,0,Infinity}]

Sum[(-1)^k/Binomial[n,k]^2,{k,0,Infinity}]

Sum[(-1)^k/Binomial[n,k]^3,{k,0,Infinity}]

(∑_(n=1)^∞)((((-1))^(n+1))/((n^k) (({{2 n}, {n}}))))

Table[Sum[(-1)^(n+1)/n^k/ Binomial[2n,n],{n,1,Infinity}],{k,5}]//ColumnForm

FullSimplify[Table[Sum[(-1)^(n+1)/n^k/ Binomial[2n,n],{n,1,Infinity}],{k,5}]]//ColumnForm

de Bruijn

s[m_,n_]:=Sum[(-1)^(k+n)Binomial[2n,k]^m,{k,0,2n}]

s[1,n]

s[2,n]

FullSimplify[s[2,n]-(2n)!/(n!)^2,{n∈Integers,n>1}]

s[3,n]

FullSimplify[s[3,n]-(3n)!/(n!)^3,{n∈Integers,n>1}]

s[4,n]

Table[s[2,n],{n,10}]

Table[s[3,n],{n,10}]

Table[s[4,n],{n,10}]

(∑_(n=1)^∞)(1/((n^k) (({{2 n}, {n}}))))

n=0

Sum[1/Binomial[2n,n],{n,Infinity}]

n=1

Sum[1/n/Binomial[2n,n],{n,Infinity}]

n=2

Sum[1/n^2/Binomial[2n,n],{n,Infinity}]

n=3

This is done in terms of polygammas, but as a complicated expression

Sum[1/n^3/Binomial[2n,n],{n,Infinity}]//FullSimplify

N[s3-(Pi Sqrt[3]/18(PolyGamma[1,1/3]-PolyGamma[1,2/3])-4/3Zeta[3]),100]

n=4

Sum[1/n^4/Binomial[2n,n],{n,Infinity}]//FunctionExpand//FullSimplify

N[{%,17/36Zeta[4]}]

n=5

These are not done in terms of polygammas

FullSimplify[Sum[1/n^5/Binomial[2n,n],{n,Infinity}]]

N[%8-Pi Sqrt[3]/432(PolyGamma[3,1/3]-PolyGamma[3,2/3])+19/3Zeta[5]-1/9Zeta[3]Pi^2,20]

n7=FullSimplify[Sum[1/n^7/Binomial[2n,n],{n,Infinity}]]

N[{n7, 11 Pi Sqrt[3]/311040(PolyGamma[5,1/3]-PolyGamma[5,2/3])- 493/24 Zeta[7]+ 1/3 Zeta[5]Pi^2+ 17/1620 Zeta[3]Pi^4},20]

(∑_(n=1)^∞)((n^k)/((({{2 n}, {n}})))), (∑_(n=1)^∞)((n^k)/((({{3 n}, {n}})))), ...

Special Cases

(∑_(n=1)^∞)((18-9 n)/((({{2 n}, {n}}))))

Sum[((18-9n)/(Binomial[2n,n])),{n,∞}]//FullSimplify

(∑_(n=0)^∞)((50 n-6)/((({{3 n}, {n}})) (2^n)))

Sum[((50n-6)/(Binomial[3n,n]2^n)),{n,0,∞}]//FullSimplify

N[%]

(∑_(n=1)^∞)((-150 (n^2)+230 n-36)/((({{3 n}, {n}})) (2^n)))

Sum[((-150(n^2)+230n-36)/(Binomial[3n,n](2^n))),{n,∞}]//FullSimplify

N[%]

NSum[((-150(n^2)+230n-36)/(Binomial[3n,n](2^n))),{n,∞}]//FullSimplify

N[Pi]

(∑_(n=1)^∞)((575 (n^2)-965 n+273)/((({{3 n}, {n}})) (2^n)))

Sum[((575(n^2)-965n+273)/(Binomial[3n,n](2^n))),{n,∞}]//FullSimplify

N[%6]

NSum[((575(n^2)-965n+273)/(Binomial[3n,n](2^n))),{n,∞}]

N[6Log[2]]

(Subscript[b, 2])(k)==(1/2) (((-1))^(k+1)) (∑_(j=1)^(k+1))(((((-1))^j) j!)/(3^j)) (Binomial[2 j, j]) (StirlingS2[k+1, j]) ((∑_(i=0)^(j-1))((3^i)/((2 i+1) (Binomial[2 i, i])))+((2 π)/(3 (Sqrt[3]))))

expr1=Table[Sum[((n^k)/(Binomial[2n,n])),{n,∞}],{k,5}]//FunctionExpand//FullSimplify//Expand

expr2=Table[((((-1))^(k+1))/2)Sum[(((-1))^j)j!StirlingS2[k+1,j]((Binomial[2j,j])/(3^j))(Sum[((3^i)/((2i+1)Binomial[2i,i])),{i,0,j-1}]+(2/(3(Sqrt[3])))π),{j,k+1}],{k,5}]//Simplify//Expand

expr1-expr2

Integrate[PolyLog[-k,x(1-x)]+2PolyLog[-k-1,x(1-x)],{x,0,1}]

Table[Integrate[PolyLog[-k,x(1-x)]+2PolyLog[-k-1,x(1-x)],{x,0,1}],{k,3}]//Timing

Integrate[PolyLog[-k-1,x(1-x)]/x,{x,0,1}]

Table[Integrate[PolyLog[-k-1,x(1-x)]/x,{x,0,1}],{k,3}]//Timing

t=Table[((((-1))^(k+1))/2)Sum[(((-1))^j)j!StirlingS2[k+1,j]((Binomial[2j,j])/(3^j))(Sum[((3^i)/((2i+1)Binomial[2i,i])),{i,0,j-1}]+(2/(3(Sqrt[3])))π),{j,k+1}],{k,20}]//Expand;

First/@t

(Sqrt[3])/π Last/@t

v5

Integrate[((4p-10)/(((1-x(1-x)))^(p-2)))-((7p-12)/(((1-x(1-x)))^(p-1)))+((3p-3)/(((1-x(1-x)))^p)),{x,0,t}]//Timing

Integrate[((4p-10)/(((1-x(1-x)))^(p-2)))-((7p-12)/(((1-x(1-x)))^(p-1)))+((3p-3)/(((1-x(1-x)))^p)),{x,0,t},Assumptions->t>0&&p∈Integers&&p>0]//FullSimplify//Timing

v6

Integrate[((4p-10)/(((1-x(1-x)))^(p-2)))-((7p-12)/(((1-x(1-x)))^(p-1)))+((3p-3)/(((1-x(1-x)))^p)),{x,0,t},Assumptions->t>0&&p∈Integers&&p>0]//FullSimplify//Timing

(Subscript[b, 3])(k)

Table[Sum[((n^k)/(Binomial[3n,n](2^n))),{n,∞}],{k,3}]//FunctionExpand//FullSimplify

c[j_,k_,3]:=((((-1))^(k+j))/j)Sum[(((-1))^m)(3m-1)(m^(k+1))Binomial[j,m],{m,j}]

Table[Sum[c[j,k,3]Integrate[(((1-x^2(1-x)/2))^(-j)),{x,0,1}],{j,6}],{k,1}]//Expand

Related Sums

(∑_(n=1)^∞)(1/((({{3 n}, {n}})) ))

Sum[(1/(Binomial[3n,n])),{n,∞}]//FunctionExpand//FullSimplify

(∑_(n=1)^∞)((((-1))^n)/((({{3 n}, {n}})) (4^n)))

Sum[((((-1))^n)/(Binomial[3n,n](4^n))),{n,∞}]//FunctionExpand//FullSimplify

N[{%,-(1/28)-(3/32)Log[2]+(13/(112(Sqrt[7])))ArcTan[((Sqrt[7])/5)]}]

(∑_(n=1)^∞)(((((-1))^n)n)/((({{3 n}, {n}})) (4^n)))

Sum[(((((-1))^n)n)/(Binomial[3n,n](4^n))),{n,∞}]//FunctionExpand//FullSimplify

N[{%,-(81/1568)-(9/256)Log[2]+(17/(6272(Sqrt[7])))ArcTan[((Sqrt[7])/5)]}]

Martin

s[x_,n_]:=Sum[(-1)^k Binomial[n,k] (x-k)^n,{k,0,n}]

Table[s[x,n],{n,5}]//ColumnForm

Simplify[%]

b[x_,0,n_]:=x^n
b[x_,k_,n_]:=Sum[Binomial[n,i]x^i(-k)^(n-i),{i,0,n}]
b[x_,k_,n_]:=(((-k))^n) (((1-(x/k)))^n)

s2[x_,n_]:=Sum[(-1)^k Binomial[n,k] b[x,k,n] ,{k,0,n}]

s2[x,n]

x^n+Sum[(-1)^k Binomial[n,k](((-k))^n) (((1-(x/k)))^n),{k,n}]

Simplify[Table[%,{n,5}]]

s1[n_]:=Sum[Binomial[n,k](-1)^k(x-k)^n,{k,0,∞}]
s2[n_]:=Sum[Binomial[n,k](-1)^k(x-k)^n,{k,0,n}]
s3[n_]:=Sum[Binomial[n,k](-1)^k(n-k)^n,{k,0,n}]

Expand[Table[s1[n]-n!,{n,5}]]

Expand[Table[s2[n]-n!,{n,5}]]

Expand[Table[s3[n]-n!,{n,5}]]

Sinyor et al. (2001)

Sum[(1/(m-ll))Binomial[m+ll-jj,2ll-jj+1]Binomial[m-ll+jj-1,jj]Binomial[m-ll,2(l-ll)-(j-jj)]Binomial[m-ll,j-jj],{ll,l},{jj,j}]

Binomial Series

Series[(a+x)^n,{x,0,5}]

n=5;
Sum[Binomial[n,k] a^k x^(n-k),{k,0,n}]

Sum[Binomial[n,k]a^k x^(n-k),{k,0,n}]

Sum[Binomial[n,k]a^(n-k) x^k,{k,0,n}]

n=.

Series[(a+x)^(-n),{x,0,5}]

Sum[Binomial[k+n-1,k] (-1)^k a^(-n-k) x^(k),{k,0,5}]

Sum[Binomial[-n,k] a^(-n-k) x^(k),{k,0,5}]

n=.

Collect[Sum[Binomial[-n,k] a^(-n-k) x^(k),{k,0,5}] /. a->1,x]

Series[1/(x-1)^n,{x,0,5}]

Collect[Sum[Binomial[-n,k] a^(-n-k) x^(k),{k,0,5}] /. a->-1,x]

Binomial[-2,3]

Table[{Binomial[-n,k],(-1)^k Binomial[k+n-1,k]},{k,0,5},{n,0,5}]

Positive Central Binomial

Sum[1/(n^k Binomial[2n,n]),{n,1,Infinity}]

Table[Sum[1/(n^k Binomial[2n,n]),{n,1,Infinity}],{k,0,4}]

Sum[1/(n^3 Binomial[2n,n]),{n,1,Infinity}]

FullSimplify[Sum[1/(n^4 Binomial[2n,n]),{n,1,Infinity}]]

Table[
{NSum[1/(n^k Binomial[2n,n]),{n,1,Infinity}],
HypergeometricPFQ[Table[1,{k+1}],Join[{3/2},Table[2,{k-1}]],1/4]/2//N},
{k,0,10}]

Erdős Power Theorem

<<IntegerSequences`

Select[Flatten[Table[{n,k},{n,2000},{k,2,n/2}],1],ExactPowerQ[Binomial@@#]&]

ExactPower[Binomial@@#]&/@%

Negative Central Binomial

Sum[(-1)^(n-1)/(n^k Binomial[2n,n]),{n,1,Infinity}]

FullSimplify[Table[Sum[(-1)^(n-1)/(n^k Binomial[2n,n]),{n,1,Infinity}],{k,0,4}]]

FullSimplify[Table[Sum[(-1)^(n-1)/(n^k Binomial[2n,n]),{n,1,Infinity}],{k,0,6}]]

Worpizky's Identity

Simplify[Table[Sum[Eulerian[n,k]Binomial[k,n]x^k,{k,n}],{n,5}]]

Simplify[Table[Sum[Eulerian[n,k]Binomial[n+k,k]x^k,{k,n}],{n,5}]]

Table[Eulerian[n,k]Binomial[k,n],{n,5},{k,n}]