二項係数の和から母関数へ

二項係数

1472

この記事では数列の母関数を考えることで，鮮やかに計算できる例を紹介します。

二項係数の和を求める

具体的に以下の問題を考えながら話を進めていきます。

二項係数の和

$n$を正の整数とする。次の和を求めなさい。
⑴　$\displaystyle \ssum_{k=0}^{n}\kumiawase{n}{k}$　　　⑵　$\displaystyle \ssum_{k=0}^{n}k\,\kumiawase{n}{k}$　　　⑶　$\displaystyle \ssum_{k=0}^{n}\bunsuu{\!\kumiawase{n}{k}}{k+1}$

まずは母関数を使わずに計算してみる

二項定理や組み合わせについて知っていれば，この問題はそれほど難しいものではありません。

⑴

⑴ですと二項定理から，
$$\ssum_{k=0}^{n}\kumiawase{n}{k}=(1+1)^n=\bm{2^n}$$
と$n$乗を考えることで計算可能です。

⑵

次に⑵についても考えたいですが，次の結果が成り立つことを用いてみます。（証明は簡単ですのでここでは省略します。）

二項係数の性質

$n$を$2$以上の整数，$k$を正の整数としたとき，次が成り立つ。$$ k\,\kumiawase{n}{k}=n\,\kumiawase{n-1}{k-1}\qquad\cdots\cdots\style{font-family:inherit}{\text{①}} $$

よって，$n$が$2$以上の整数ならば，
\begin{align} \ssum_{k=0}^{n}k\,\kumiawase{n}{k}&=\ssum_{k=1}^{n}k\,\kumiawase{n}{k}\\&=\ssum_{k=1}^{n}n\,\kumiawase{n-1}{k-1}\\ &=n\ssum_{k=1}^{n}\kumiawase{n-1}{k-1}\\ &=n\ssum_{k=0}^{n-1}\kumiawase{n-1}{k}\\ &={n\cdot2^{n-1}} \end{align}
と計算できます。途中で$\ssum$の番号をずらしたりしていますが，$\ssum$の意味に立ち返れば簡単な式変形です。また$n=1$のときは$\ssum_{k=0}^{1}k\,\kumiawase{1}{k}=1$ですので，すべての正の整数$n$に対して$$ \ssum_{k=0}^{n}k\,\kumiawase{n}{k}=\bm{n\cdot2^{n-1}} $$
であることも分かりました。

⑶

最後に⑶を考えます。補題 1 の①式より，正の整数$n$と$0$以上の整数$k$に対して
$$ (k+1)\kumiawase{n+1}{k+1}=(n+1)\kumiawase{n}{k} $$
が成り立ちますので，$$ \bunsuu{\kumiawase{n}{k}}{k+1}=\bunsuu{\kumiawase{n+1}{k+1}}{n+1} $$
です。よって⑵と同様に式変形をしていけば，おのずと$$ \ssum_{k=0}^{n}\bunsuu{\!\kumiawase{n}{k}}{k+1}=\bm{\bunsuu{2^{n+1}-1}{n+1}} $$
と計算できます。

次に母関数を用いてみる

そもそも数列の母関数ってなんだっけ？という場合がありますので，一応定義しておきます。

有限数列の母関数

有限数列$\suuretu{a_k}_{k=0}^{n}$の 母関数 とは，$$ a_0+a_1x+a_2x^2+\cdots\cdots+a_nx^n\;\left(=\ssum_{k=0}^{n}a_kx^k\right) $$
という$n$次関数のことを言う。

母関数を用いて先ほどの問題に別解を与えてみます。

⑴

まずは⑴です。数列$\suuretu{\kumiawase{n}{k}}_{k=0}^n$の母関数が$(1+x)^n$である，というのが二項定理の主張でした。つまり，$$ \ssum_{k=0}^{n}\kumiawase{n}{k}x^k=(1+x)^n\qquad\cdots\cdots\!\!\!\style{font-family:inherit}{\text{（⭐）}} $$
です。この⭐式に$x=1$を代入すれば$$ \ssum_{k=0}^{n}\kumiawase{n}{k}=2^n $$
と求められます。

⑵，⑶を鮮やかに

次に⑵について考えてみましょう。⑵では$k\,\kumiawase{n}{k}$という形の和を求めたいです。というわけで，⭐式の 両辺を$\bm x$で微分 してみましょう。すると，次の等式を得ます。$$ \ssum_{k=0}^{n}\kumiawase{n}{k}\cdot k\,x^{k-1}=n(1+x)^{n-1} $$（有限和なのでΣと微分の順序交換を気にしなくていいですね。爽快な気分です。）
ここに$x=1$を代入することで，$$ \ssum_{k=0}^{n}\kumiawase{n}{k}\cdot k=n\cdot 2^{n-1} $$と⑵の結果が鮮やかに求められます！母関数を考えることで微分という演算が可能になり，ここまで綺麗に求められるのです。

では⑶はどうするのだろうというと，積分を実行してみたいです。特に⭐式の両辺を$0$から$1$まで積分してみましょう。すると，$$ \int_{0}^1 \left(\ssum_{k=0}^{n}\kumiawase{n}{k}x^k\right)\,dx=\int_0^1 (1+x)^n\,dx $$
となります。（有限和なのでΣと積分の順序交換を気にせず変形できます。最高。）
それぞれの左辺と右辺を計算することで，$$ \ssum_{k=0}^{n}\bunsuu{\!\kumiawase{n}{k}}{k+1}={\bunsuu{2^{n+1}-1}{n+1}} $$
を得ます。これが⑶の答えです。

数列に対して関数を考えることで，微分や積分といった操作が可能になり，より複雑な級数の和を求めることができるようになります。逆に母関数を弄ることで新たな級数の和を発見できるかもしれません。これは母関数を考える1つの利点と言えるでしょう。

利用例：少し面倒な級数

先程の⑵の類似として，次の和を計算してみます。$$ \ssum_{k=0}^{n}k^2\,\kumiawase{n}{k} $$
これを考えるために，やはり⭐式から始めてみましょう。⭐式を$x$で微分すると，$$ \ssum_{k=0}^{n}\kumiawase{n}{k}\cdot k\,x^{k-1}=n(1+x)^{n-1} $$
と計算できました。この両辺に$x$をかけて，$$ \ssum_{k=0}^{n}\kumiawase{n}{k}\cdot k\,x^{k}=nx(1+x)^{n-1} $$
です。さらにこの両辺を$x$で微分します。すると，$$ \ssum_{k=0}^{n}\kumiawase{n}{k}\cdot k^2\,x^{k-1}=n(1+x)^{n-1}+n(n-1)x(1+x)^{n-2} $$
となります。この式に$x=1$を代入することで，\begin{align} \ssum_{k=0}^{n}k^2\,\kumiawase{n}{k}&=n\cdot 2^{n-1}+n(n-1)\cdot 2^{n-2}\\ &=n(n+1)2^{n-2} \end{align}
と計算できました。このように微分して$x$を掛ける操作を繰り返すことで，複雑（だがキレイ）な和を求めることが出来ます。

利用例：等差×等比

母関数の考えを用いて$\ssum_{k=0}^nk\cdot3^{k}$を計算してみます。まず次の等式（等比数列の和）を考えます。$$ \ssum_{k=0}^n x^{k}=\bunsuu{x^{n+1}-1}{x-1} $$
この両辺を微分して，$$ \ssum_{k=0}^n k\cdot x^{k-1}=\bunsuu{(n+1)x^{n}(x-1)-(x^{n+1}-1)}{(x-1)^2} $$
この両辺に$x$をかけ，$x=3$を代入することで，
\begin{align} \ssum_{k=0}^nk\cdot3^{k}&=\bunsuu{n(n+1)3^{n+1}\cdot 2-3^{n+2}+3}{4} \end{align}
と求められます。