今回はクヌース先生のコンピュータの数学(Amazon)の中で見つけた二項係数の和の定理を紹介します。
【例題 １】以下の二項係数の和の一般解を求めよ
\begin{align}
&\sum_{k=0}^{n}\binom{r+k}{k} &(1) \\ \\
&\sum_{k=0}^{n}\binom{k}{m} &(2) \\ \\
\end{align}
パスカルの三角形の式
この例題を有名なパスカルの三角形の式を使って求めます。
\begin{align}
\binom{r}{k} &= \color{blue}{\binom{r-1}{k}} + \color{red}{\binom{r-1}{k-1}} &(3) \\ \\
\end{align}
例題 １－(1) の解法
具体的な例として$\large \binom{5}{3}$を$\color{red}{赤字}$の部分に(3)を次々に使って展開していきます。
\begin{align}
\color{black}{\binom{5}{3}}&=\color{blue}{\binom{4}{3}}+\color{red}{\binom{4}{2}}\\
&=\binom{4}{3}+\color{blue}{\binom{3}{2}}+\color{red}{\binom{3}{2}}\\
&=\binom{4}{3}+\binom{3}{2}+\color{blue}{\binom{2}{1}}+\color{red}{\binom{1}{0}} & \\
&この右辺を見ると(1)のr=1, n = 3の場合なので、 & \\
&\sum_{k=0}^{n}\binom{r+k}{k}=\binom{r+n+1}{n} &(1a) \\ \\
&となります。（帰納法を使えば証明可） & \\
\end{align}
例題 １－(２) の解法
今度は$\large \binom{5}{3}$の$\color{blue}{青字}$の部分を(3)を使って展開していきます。
\begin{align}
\color{black}{\binom{5}{3}}&=\color{blue}{\binom{4}{3}}+\color{red}{\binom{4}{2}}\\
&=\color{blue}{\binom{3}{3}}+\color{red}{\binom{3}{2}}+\color{black}{\binom{4}{2}}\\
&=\color{blue}{\binom{2}{3}}+\color{red}{\binom{2}{2}}+\color{black}{\binom{3}{2}}+\color{black}{\binom{4}{2}} & \\
&=\color{blue}{\binom{1}{3}}+\color{red}{\binom{1}{2}}+\color{black}{\binom{2}{2}}+\color{black}{\binom{3}{2}}+\color{black}{\binom{4}{2}} & \\
&=\color{blue}{\binom{0}{3}}+\color{red}{\binom{0}{2}}+\color{black}{\binom{1}{2}}+\color{black}{\binom{2}{2}}+\color{black}{\binom{3}{2}}+\color{black}{\binom{4}{2}} & \\
&\binom{0}{3}=0なので無視すると、 & \\
&(2)のm=2, n = ４の場合になっていることがわかります、 & \\
&したがって、 & \\
&\sum_{k=0}^{n}\binom{k}{m}=\binom{n+1}{m+1} &(2a) \\ \\
&となります。（これも帰納法を使えば証明可） & \\
\end{align}
【例題 ２】以下の二項係数の和の一般解を求めよ
シグマの上限が$n$でないことに注意して下さい。
\begin{align}
&\sum_{k=1}^{x}\binom{n-k}{m} &(3) \\ \\
\end{align}
例題 ２ の解法
\begin{align}
& j=n-kと置き換えると& \\
& k=1 \ \ \rightarrow \ \ j=n-1& \\
& k=x \ \ \rightarrow \ \ j=n-x& \\
\sum_{k=1}^{x}\binom{n-k}{m}&=\sum_{j=n-k}^{n-1}\binom{j}{m} & \\
&=\sum_{j=0}^{n-1}\binom{j}{m}-\sum_{j=0}^{n-x-1}\binom{j}{m} &(3') \\
& これに(2a)を適用すると& \\
&=\binom{n}{m+1}-\binom{n-x}{m+1} &(3a) \\
&となります。 & \\
\\ \\
\end{align}
この考え方はProject Euler, Problem 756: Approximating a Sumを解くのに役に立ちます。