0

z変換:二項係数C(n,k)の総和が2^nであることの証明

45
0
$$\newcommand{BEQ}[0]{\begin{eqnarray}} \newcommand{C}[0]{\mathbb{C}} \newcommand{ceil}[1]{\left\lceil#1\right\rceil} \newcommand{div}[0]{\mathrm{div}} \newcommand{division}[0]{÷} \newcommand{EEQ}[0]{\end{eqnarray}} \newcommand{floor}[1]{ \left\lfloor#1\right\rfloor} \newcommand{FT}[1]{ \mathcal{F}\left[#1\right]} \newcommand{grad}[0]{\mathrm{grad}\ } \newcommand{hgf}[5]{{}_{#1}F_{#2}\left(\genfrac{}{}{0pt}{}{#3}{#4}\,;\,#5\right)} \newcommand{IFT}[1]{ \mathcal{F^{-1}}\left[#1\right]} \newcommand{ILT}[1]{\mathcal{L^{-1}}\left[#1\right]} \newcommand{Iz}[0]{\int_z^{\infty} } \newcommand{IZT}[1]{\mathcal{Z^{-1}}\left[#1\right]} \newcommand{LT}[1]{\mathcal{L}\left[#1\right]} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{rot}[0]{\mathrm{rot}\ } \newcommand{SI}[1]{\sum_{#1=1}^{\infty}} \newcommand{SO}[1]{\sum_{#1 = 0}^{\infty}} \newcommand{Z}[0]{\mathbb{Z}} \newcommand{ZT}[1]{\mathcal{Z}\left[#1\right]} $$

二項係数$C(n,k)$の総和が$2^n$になることを二項定理、もしくは$z$変換を用いて証明する。

二項係数の総和は$2^n$

二項係数の総和は$2^n$である。つまり次式である。
$$ \sum_{k=0}^{n}\binom{n}{k}=2^n $$
なお$\binom{n}{k}:=C(n,k)$

二項定理を用いた証明

二項定理は
$$ (a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k} b^k $$である。このとき、$a=b=1$とおくと
$$ 2^n=\sum_{k=0}^{n}\binom{n}{k}1^{n-k} 1^k=\sum_{k=0}^{n}\binom{n}{k} $$となり命題が示された。

$z$変換を用いた証明【1】

$\binom{n}{k}$$k$$n$より大きい時、0であることに注意すると左辺は
$$ \sum_{k=0}^{n}\binom{n}{k}=\sum_{k=0}^{\infty}\binom{n}{k} $$となる。これを$z$変換して
$$ \BEQ \ZT{\sum_{k=0}^{\infty}\binom{n}{k}} &=&\sum_{k=0}^{\infty}\ZT{\binom{n}{k}}\\ &=&\sum_{k=0}^{\infty}\frac{z}{(z-1)^{k+1}}\\ &=&\frac{z}{(z-1)}\sum_{k=0}^{\infty}\frac{1}{(z-1)^{k}}\\ &=&\frac{z}{(z-1)}\dfrac1{1-\frac1{z-1}}\\ &=&\frac{z}{(z-1)}\dfrac{z-1}{z-1-1}\\ &=&\frac{z}{z-2}\\ \EEQ $$
なお、$\ZT{\binom{n}{k}}=\frac{z}{(z-1)^{k+1}} $を用いた。
両辺を逆$z$変換して
$$ \sum_{k=0}^{\infty}\binom{n}{k}=\IZT{\frac{z}{z-2}}=2^n $$
となり命題が示された。

$z$変換を用いた証明【2】

$$ f(n):=\sum_{k=0}^{n}\binom{n}{k} $$とおく。
両辺を$n!$で割って
$$ \BEQ \frac{f(n)}{n!} &=& \frac1{n!} \sum_{k=0}^{n}\frac{n!}{k!(n-k)!}\\ &=& \sum_{k=0}^{n}\frac{1}{k!(n-k)!}\\ \EEQ $$両辺を$z$変換して
$$ \BEQ \ZT{\frac{f(n)}{n!}} &=&\ZT{\sum_{k=0}^{n}\frac{1}{k!(n-k)!}}\\ &=&\ZT{\frac1{n!}}\ZT{\frac1{n!}}\\ &=&e^{\frac1z}e^{\frac1z}\\ &=&e^{\frac2z}\\ &=&\ZT{\frac{2^n}{n!}} \EEQ $$
なお、$z$変換の畳み込み則、および$z$変換のスケーリング則を用いた。
両辺を逆$z$変換して
$$ \BEQ \frac{f(n)}{n!}&=&\frac{2^n}{n!}\\ \\ \therefore f(n)&=&2^n \EEQ $$となり命題が示された。

投稿日:2022105

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

zeta
32
2486

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中