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

二項定理より

$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$

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

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

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

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

$A$ の部分集合のうち要素数が奇数のものを全て集めた集合を $B_1$，要素数が偶数のものを全て集めた集合を $B_2$ とする。

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

具体的には，$B_1$ の集合に対して $a_1$ を「交換」（あれば除く，なければ追加）することで $B_2$ の集合が対応する。これは一対一対応になる。

図のような格子状の道において，$(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$ 通り）

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

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

$\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$ より目標の式を得る。

$(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)$

両辺 $x$ で微分する。その際に積の微分公式を使う：

$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)$

$x^{n-1}$ の係数を比較する。左辺は，$2n{}_{2n-1}\mathrm{C}_{n-1}$

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

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

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

これと

${}_{2n}\mathrm{C}_n=\dfrac{(2n)!}{n!n!}=\dfrac{(2n-1)!}{(n-1)!n!}\times 2=2{}_{2n-1}\mathrm{C}_{n-1}$

より目標の式を得る。