\def\bi(#1,#2){{}_{#1}\!\mathrm{C}_{#2}}
\def\fraction(#1/#2){\frac{#1}{#2}}
二項係数
二項係数は，次のように定義しておく。
\bi(a,b) := \fraction(a!/{(a-b)!b!})
\qquad
(a \geq b)
二項係数の和
\bi(n,0) + \bi(n,1) + \bi(n,2) + \bi(n,3) + \cdots + \bi(n,n)
=
2^n
\bi(n,0) - \bi(n,1) + \bi(n,2) - \bi(n,3) + \cdots (-1)^n \bi(n,n)
=
0
つまり
\sum_{k=0}^n \bi(n,k) =2^n
\\
\sum_{k=0}^n (-1)^k \bi(n,k) =0
証明
\begin{eqnarray}
(1+x)^n = \sum_{k=0}^n \bi(n,k) x^k
\end{eqnarray}
両辺のxに1を代入して，証明終了。
\begin{eqnarray}
(1-x)^n = \sum_{k=0}^n \bi(n,k) (-1)^k x^k
\end{eqnarray}
両辺のxに1を代入して，証明終了。
帰納法による証明
「ただいま編集中」
係数つき二項係数
$$
\sum _{k=1}^n k \bi(n,k) = 2^{n-1} n
$$
$$
\sum_{k=1}^{n-1} (-1)^k k \bi(n,k) = (-1)^n (-n)
$$
直接的な証明
\begin{eqnarray}
k \bi(n,k)
&=&
k \fraction(n!/{(n-k)! k!})\\
&=& \fraction(n!/{(n-k)! (k-1)!}) \\
&=& n\fraction({(n-1)!}/{(n-1-[k-1])! (k-1)!}) \\
&=& n \bi(n-1,k-1) \\
\end{eqnarray}
\begin{eqnarray}
\sum _{k=1}^n k \bi(n,k)
&=& \sum _{k=1}^n \bi(n-1,k-1) n \\
&=& 2^{n-1} n
\end{eqnarray}
\begin{eqnarray}
\sum _{k=1}^n (-1)^k k \bi(n,k)
&=& \sum _{k=1}^n (-1)^k \bi(n-1,k-1) n \\
&=& 0
\end{eqnarray}
\sum _{k=1}^{n-1} (-1)^k k \bi(n,k) = - (-1)^{n} n \bi(n,n)
より示せた。
多項式を微分する証明
\begin{eqnarray}
(1-x)^n = \sum_{k=0}^n \bi(n,k) (-1)^k x^k
\end{eqnarray}
両辺をxで微分して
\begin{eqnarray}
-n (1-x)^{n-1} = \sum_{k=1}^n k \cdot \bi(n,k) (-1)^k x^{k-1}
\end{eqnarray}
1 を代入する
\begin{eqnarray}
0 &=& \sum_{k=1}^n k \bi(n,k) (-1)^k
\\
\sum_{k=1}^{n-1} k \bi(n,k) (-1)^k &=& - n \bi(n,n)(-1)^n
\end{eqnarray}
和をとる範囲に注意して頂きたい。
二項係数の積の和
次のような和を考える。右辺は計算結果。
-\bi(2,1)
=
-2
-\bi(3,1) + \bi(3,2)\bi(2,1)
=
3
-\bi(4,1) + \bi(4,2)\bi(2,1) + \bi(4,3)\bi(3,1) - \bi(4,3)\bi(3,2)\bi(2,1)
=
-4
\begin{eqnarray}
&&-\bi(5,1)
\\
&&+ \bi(5,2)\bi(2,1) + \bi(5,3)\bi(3,1) + \bi(5,4)\bi(4,1)
\\
&&- \bi(5,3)\bi(3,2)\bi(2,1) - \bi(5,4)\bi(4,3)\bi(3,1) - \bi(5,4)\bi(4,2)\bi(2,1)
\\
&&+ \bi(5,4)\bi(4,3)\bi(3,2)\bi(2,1)
\\
&&=5
\end{eqnarray}
うまく表記することが難しいが，$k\geq 2$に対して一般に次のような等式が成立する
\begin{eqnarray}
&&-\bi(k,1)\\
&&+ \bi(k,2)\bi(2,1) + \bi(k,3)\bi(3,1) +\cdots +\bi(k,k-1)\bi(k-1,1)\\
&&\vdots \\
&& + (-1)^j \sum_{a_1-a_j = k-1, a1 > a_2 > \cdots > a_j} \prod _{i=1}^j \bi(a_i,a_{i-1})
\\
&& \vdots\\
&&+ (-1)^{k-1} \bi(k,k-1)\bi(k-1,k-2) \cdots \bi(2,1)\\
&&=(-1)^k (-k)
\end{eqnarray}
証明は帰納法で行う。表記が煩雑になるので，記号を導入する。
\begin{eqnarray}
S_k
&:=&-\bi(k,1)\\
&&+ \bi(k,2)\bi(2,1) + \bi(k,3)\bi(3,1) +\cdots +\bi(k,k-1)\bi(k-1,1)\\
&&\vdots \\
&& + (-1)^j \sum_{a_1-a_j = k-1, a1 > a_2 > \cdots > a_j} \prod _{i=1}^j \bi(a_i,a_{i-1})
\\
&& \vdots\\
&&+ (-1)^{k-1} \bi(k,k-1)\bi(k-1,k-2) \cdots \bi(2,1)\\
&&=(-1)^k (-k)
\end{eqnarray}
S_1, S_2,... ,S_kで成立していると仮定。
\begin{eqnarray}
S_{k+1}
&=&-\bi(k+1,1)\\
&&- \bi(k+1,k) S_k\\
&&- \bi(k+1,k-1) S_{k-1}\\
&&\vdots \\
&& - \bi(k+1,1) S_2\\
&&= \sum_{j=1}^k \bi(k+1,j) (-1)^j (-j)
\\
&&= (-1)^{k+1}(k+1)
\end{eqnarray}