二項係数の和,二乗和,三乗和

二項係数の総和,二乗和,三乗和に関する美しい公式を解説します。

nn00 以上の任意の整数とします。

二項係数の和

k=0nnCk=2n\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k=2^n

k=0n(1)knCk=0(n1)\displaystyle\sum_{k=0}^n(-1)^k{}_n\mathrm{C}_k=0\:(n\geqq 1)

例えば n=4n=4 のとき,

4C0+4C1+4C2+4C3+4C4=1+4+6+4+1=24{}_4\mathrm{C}_0+{}_4\mathrm{C}_1+{}_4\mathrm{C}_2+{}_4\mathrm{C}_3+{}_4\mathrm{C}_4\\ =1+4+6+4+1\\ =2^4

4C04C1+4C24C3+4C4=14+64+1=0{}_4\mathrm{C}_0-{}_4\mathrm{C}_1+{}_4\mathrm{C}_2-{}_4\mathrm{C}_3+{}_4\mathrm{C}_4\\ =1-4+6-4+1\\ =0

となっています。

証明は二項定理を使うだけで簡単にできます。

証明1

二項定理より

2n=(1+1)n=k=0nnCk1k1nk=k=0nnCk2^n=(1+1)^n\\ =\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k1^k1^{n-k}\\ =\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k

後半の式も同様。

0=(1+1)n=k=0nnCk(1)k1nk=k=0n(1)knCk0=(-1+1)^n\\ =\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k(-1)^k1^{n-k}\\ =\displaystyle\sum_{k=0}^n(-1)^k{}_n\mathrm{C}_k

「部分集合の個数」を数えることでも証明できます。

証明2

「集合 A={a1,a2,,an}A=\{a_1,a_2,\dots,a_n\} の部分集合の個数 NN」を2通りの方法で数える。

  • 全ての要素について「含める」or「含めない」の2通りなので,N=2nN=2^n

  • 要素数が kk である部分集合の個数は nCk{}_{n}\mathrm{C}_k である。これを k=0k=0 から k=nk=n まで足し上げると,N=k=0nnCkN=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k

また,後半の式も似たように考えることができる。

AA の部分集合のうち要素数が奇数のものを全て集めた集合を B1B_1,要素数が偶数のものを全て集めた集合を B2B_2 とする。

B1=B2|B_1|=|B_2| を証明すればよい。これは,特定の要素を「交換」するという一対一対応を構成できることからわかる。

具体的には,B1B_1 の集合に対して a1a_1 を「交換」(あれば除く,なければ追加)することで B2B_2 の集合が対応する。これは一対一対応になる。

※証明2の後半部分は「松坂和夫先生の集合・位相入門」という本を参考にしました。

→高校数学の問題集 ~最短で得点力を上げるために~のT87では,帰納法による別の証明や,計算ミスをしないためのコツも解説しています。

二項係数の二乗和

k=0n(nCk)2=2nCn\displaystyle\sum_{k=0}^n({}_n\mathrm{C}_k)^2={}_{2n}\mathrm{C}_n

例えば n=3n=3 のとき,6C3=20{}_6\mathrm{C}_3=20(3C0)2+(3C1)2+(3C2)2+(3C3)2=12+32+32+12=20({}_3\mathrm{C}_0)^2+({}_3\mathrm{C}_1)^2+({}_3\mathrm{C}_2)^2+({}_3\mathrm{C}_3)^2\\ =1^2+3^2+3^2+1^2\\ =20

となり一致しています。2通りの証明を紹介します。

証明1

二項係数の二乗和

図のような格子状の道において,(0,0)(0,0) から (n,n)(n,n) までの最短経路の数を2通りの方法で数える。

  • nn 個の「右」と nn 個の「上」を並べる場合の数に等しいので,2nCn{}_{2n}\mathrm{C}_n 通り。

  • 途中で (0,n),(1,n1),,(n,0)(0,n),(1,n-1),\cdots, (n,0) を必ず1つだけ通る。そして,(k,nk)(k,n-k) を通る最短経路の数は,(nCk)2({}_n\mathrm{C}_k)^2 である。((k,nk)(k,n-k) まで行く方法がnCk{}_n\mathrm{C}_k 通り,そこから (n,n)(n,n) まで行く方法も nCk{}_n\mathrm{C}_k 通り)

よって,目標の式は示された。

証明2

ヴァンデルモンドの畳み込みで証明した式:

k=0npCkqCnk=p+qCn\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k{}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n

において,p=n,q=np=n,q=n とすると,

k=0nnCknCnk=2nCn\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k{}_n\mathrm{C}_{n-k}={}_{2n}\mathrm{C}_n

を得る。これと nCnk=nCk{}_n\mathrm{C}_{n-k}={}_n\mathrm{C}_k より目標の式を得る。

変形版

k=0nk(nCk)2=n22nCn\displaystyle\sum_{k=0}^nk({}_n\mathrm{C}_k)^2=\dfrac{n}{2}{}_{2n}\mathrm{C}_n

証明

(1+x)2n=(1+x)n(1+x)n=(k=0nnCkxk)(k=0nnCkxk)(1+x)^{2n}\\ =(1+x)^n(1+x)^n\\ =\left(\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_kx^k\right)\left(\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_kx^k\right)

両辺 xx で微分する。その際に積の微分公式を使う:

2n(1+x)2n1=2(k=0nnCkxk)(k=1nnCkkxk1)2n(1+x)^{2n-1}\\ =2\left(\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_kx^k\right)\left(\displaystyle\sum_{k=1}^n{}_n\mathrm{C}_kkx^{k-1}\right)

xn1x^{n-1} の係数を比較する。左辺は,2n2n1Cn12n{}_{2n-1}\mathrm{C}_{n-1}

右辺は,1つめのシグマが k=ntk=n-t,2つめのシグマが k=tk=t のとき nn 乗が登場するので

2t=1nnCtxntnCttxt12\displaystyle\sum_{t=1}^n{}_n\mathrm{C}_tx^{n-t}{}_n\mathrm{C}_{t}tx^{t-1}

よって,n2n1Cn1=t=1ntnCt2n{}_{2n-1}\mathrm{C}_{n-1}=\displaystyle\sum_{t=1}^nt{}_n\mathrm{C}_t^2

これと

2nCn=(2n)!n!n!=(2n1)!(n1)!n!×2=22n1Cn1{}_{2n}\mathrm{C}_n=\dfrac{(2n)!}{n!n!}=\dfrac{(2n-1)!}{(n-1)!n!}\times 2=2{}_{2n-1}\mathrm{C}_{n-1}

より目標の式を得る。

二項係数の三乗和

Dixonの恒等式

k=nn(1)k(2nCn+k)3=(3n)!(n!)3\displaystyle\sum_{k=-n}^n(-1)^k({}_{2n}\mathrm{C}_{n+k})^3=\dfrac{(3n)!}{(n!)^3}

例えば n=2n=2 のとき,

(4C0)3(4C1)3+(4C2)3(4C3)3+(4C4)3=164+21664+1=90({}_4\mathrm{C}_0)^3-({}_4\mathrm{C}_1)^3+({}_4\mathrm{C}_2)^3-({}_4\mathrm{C}_3)^3+({}_4\mathrm{C}_4)^3\\=1-64+216-64+1=90

6!(2!)3=90\dfrac{6!}{(2!)^3}=90

となり一致しています。

証明は難しいようです。

追記:せきゅーん氏が証明を教えて下さいました: ディクソンの恒等式 - インテジャーズ

シンプルで非自明な恒等式が大好きです。

Tag:数列の和を計算するための公式まとめ