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

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

$(\genfrac{}{}{0ex}{}{n}{k})$は$k$が$n$より大きい時、0であることに注意すると左辺は
$$\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})=\sum _{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n}{k})$$となる。これを$z$変換して
$$\begin{array}{rcl}\mathcal{Z}\left[\sum _{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n}{k})\right]& =& \sum _{k=0}^{\mathrm{\infty }}\mathcal{Z}\left[(\genfrac{}{}{0ex}{}{n}{k})\right]\\ & =& \sum _{k=0}^{\mathrm{\infty }}\frac{z}{(z-1{)}^{k+1}}\\ & =& \frac{z}{(z-1)}\sum _{k=0}^{\mathrm{\infty }}\frac{1}{(z-1{)}^k}\\ & =& \frac{z}{(z-1)}{\displaystyle \frac{1}{1-\frac{1}{z-1}}}\\ & =& \frac{z}{(z-1)}{\displaystyle \frac{z-1}{z-1-1}}\\ & =& \frac{z}{z-2}\end{array}$$
なお、$\mathcal{Z}\left[(\genfrac{}{}{0ex}{}{n}{k})\right]=\frac{z}{(z-1{)}^{k+1}}$を用いた。
両辺を逆$z$変換して
$$\sum _{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n}{k})={\mathcal{Z}}^{\mathcal{-}\mathcal{1}}\left[\frac{z}{z-2}\right]=2^n$$
となり命題が示された。

$$f(n):=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})$$とおく。
両辺を$n!$で割って
$$\begin{array}{rcl}\frac{f(n)}{n!}& =& \frac{1}{n!}\sum _{k=0}^n\frac{n!}{k!(n-k)!}\\ & =& \sum _{k=0}^n\frac{1}{k!(n-k)!}\end{array}$$両辺を$z$変換して
$$\begin{array}{rcl}\mathcal{Z}\left[\frac{f(n)}{n!}\right]& =& \mathcal{Z}\left[\sum _{k=0}^n\frac{1}{k!(n-k)!}\right]\\ & =& \mathcal{Z}\left[\frac{1}{n!}\right]\mathcal{Z}\left[\frac{1}{n!}\right]\\ & =& e^{\frac{1}{z}}{e}^{\frac{1}{z}}\\ & =& e^{\frac{2}{z}}\\ & =& \mathcal{Z}\left[\frac{2^n}{n!}\right]\end{array}$$
なお、$z$変換の畳み込み則、および$z$変換のスケーリング則を用いた。
両辺を逆$z$変換して
$$\begin{array}{rcl}\frac{f(n)}{n!}& =& \frac{2^n}{n!}\\ \\ \therefore f(n)& =& 2^n\end{array}$$となり命題が示された。