二項係数についての等式


\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}