z変換:二項係数C(n,k)の総和が2^nであることの証明
二項係数$C(n,k)$の総和が$2^n$になることを二項定理、もしくは$z$変換を用いて証明する。
二項係数の総和は$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}
$$となり命題が示された。
$\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
$$
となり命題が示された。
$$
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
$$となり命題が示された。
