二項係数の総和,二乗和,三乗和に関する美しい公式を解説します。
$n$ は $0$ 以上の任意の整数とします。
二項係数の和
$\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k=2^n$
$\displaystyle\sum_{k=0}^n(-1)^k{}_n\mathrm{C}_k=0$
例えば $n=4$ のとき,
${}_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$
${}_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$
となっています。
証明は二項定理を使うだけで簡単にできます。
証明
二項定理より
$2^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=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k(-1)^k1^{n-k}=\displaystyle\sum_{k=0}^n(-1)^k{}_n\mathrm{C}_k$
二項係数の二乗和
$\displaystyle\sum_{k=0}^n({}_n\mathrm{C}_k)^2={}_{2n}\mathrm{C}_n$
例えば $n=3$ のとき,${}_6\mathrm{C}_3=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)$ から$(n,n)$ までの最短経路の数を2通りの方法で数える。
- $n$ 個の「右」と $n$ 個の「上」を並べる場合の数に等しいので,${}_{2n}\mathrm{C}_n$ 通り。
- 途中で$(0,n),(1,n-1),\cdots, (n,0)$ を必ず1つだけ通る。そして,$(k,n-k)$ を通る最短経路の数は,$({}_n\mathrm{C}_k)^2$ である。($(k,n-k)$ まで行く方法が${}_n\mathrm{C}_k$ 通り,そこから$(n,n)$ まで行く方法も${}_n\mathrm{C}_k$ 通り)
よって,目標の式は示された。
証明2
ヴァンデルモンドの畳み込みで証明した式:
$\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k{}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n$
において,$p=n,q=n$ とすると,
$\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k{}_n\mathrm{C}_{n-k}={}_{2n}\mathrm{C}_n$
を得る。これと${}_n\mathrm{C}_{n-k}={}_n\mathrm{C}_k$ より目標の式を得る。
二項係数の三乗和
Dixonの恒等式:
$\displaystyle\sum_{k=-n}^n(-1)^k({}_{2n}\mathrm{C}_{n+k})^3=\dfrac{(3n)!}{(n!)^3}$
例えば $n=2$ のとき,
$({}_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$
$\dfrac{6!}{(2!)^3}=90$
となり一致しています。
証明は難しいようです。
追記:せきゅーん氏が証明を教えて下さいました:
ディクソンの恒等式 – インテジャーズ
Tag: 数列の和を計算するための公式まとめ