PRML 演習問題2.3 解答

##問題
>この演習問題では,二項分布(2.9)が正規化されていることを証明する.まず,全部で*N*個ある対象から*m*個の同じものを選ぶ組み合わせの定義(2.10)を用いて,

```math
\begin{pmatrix}
N\\
m
\end{pmatrix}
+
\begin{pmatrix}
N\\
m-1
\end{pmatrix}
=
\begin{pmatrix}
N+1\\
m
\end{pmatrix}
\tag{2.262}
```
>を示せ.この結果を用い帰納法で次の結果を証明せよ.

```math
\begin{align*}
\mathrm{(1+x)^N=\sum^N_{m=0}}
\begin{pmatrix}
N\\
m
\end{pmatrix}
\mathrm{x^m}
\tag{2.263}
\end{align*}
```
>これは**二項定理(binominal theorem)**として知られ,すべての実数値xについて成り立つ.最後に,二項分布が次のように正規化されていることを$\mathrm{(1-\mu)^N}$を和の外に出してから,二項定理を使うことで示せ.

```math
\begin{align*}
\mathrm{\sum^N_{m=0}}
\begin{pmatrix}
N\\
m
\end{pmatrix}
\mathrm{\mu^m(1-\mu)^{N-m}=1}
\tag{2.264}
\end{align*}
```
##方針
この問題は二項分布が正規化されていることを、3つの式に関して証明することで示そうというものである。誘導にのることで簡単に証明できるようなので、与えられた誘導通り問題を解き進めていく。
問題中で出てきた(2.9), (2.10)を以下に示す。

```math
\begin{align*}
Bin\mathrm{(m\mid{N,\mu})}
=
\begin{pmatrix}
N\\
m
\end{pmatrix}
\mathrm{\mu^m(1-\mu)^{N-m}}
\tag{2.9}\\
\begin{pmatrix}
N\\
m
\end{pmatrix}
\mathrm{\equiv\frac{N!}{(N-m)!m!}}
\tag{2.10}
\end{align*}
```

まず(2.262)から示す。

##(2.262)の証明
```math
\begin{pmatrix}
N\\
m
\end{pmatrix}
+
\begin{pmatrix}
N\\
m-1
\end{pmatrix}
=
\begin{pmatrix}
N+1\\
m
\end{pmatrix}
\tag{2.262}
```
を(2.10)を用いて証明する。

```math
\begin{align*}
左辺&=
\begin{pmatrix}
N\\
m
\end{pmatrix}
+
\begin{pmatrix}
N\\
m-1
\end{pmatrix}\\
&=\mathrm{\frac{N!}{(N-m)!m!}}+\mathrm{\frac{N!}{\bigl\{N-(m-1)\bigr\}!(m-1)!}}\\
&=\mathrm{\frac{N!}{(N-m)!m!}}+\mathrm{\frac{N!}{(N+1-m)!(m-1)!}}\\
&=\mathrm{\frac{(N+1-m)N!}{(N+1-m)!m!}}+\mathrm{\frac{mN!}{(N+1-m)!m!}}\\
&=\mathrm{\frac{(N+1)N!}{(N+1-m)!m!}}
\end{align*}
```

```math
\begin{align*}
右辺&=
\begin{pmatrix}
N+1\\
m
\end{pmatrix}\\
&=\mathrm{\frac{(N+1)N!}{(N+1-m)!m!}}
\end{align*}
```
したがって**左辺=右辺**より(2.262)は示された。

##(2.263)の証明
帰納法を用いて証明を行うため、まず$\mathbf{N=1}$のときに(2.263)が成り立つかを示す。次に$\mathbf{N}$が任意の数$\mathbf{k}$で(2.263)が成り立つと仮定し、$\mathbf{N=k+1}$でも同様に(2.263)が成り立つ事を示す。

```math
\begin{align*}
\mathrm{(1+x)^N=\sum^N_{m=0}}
\begin{pmatrix}
N\\
m
\end{pmatrix}
\mathrm{x^m}
\tag{2.263}
\end{align*}
```

$\mathbf{N=1}$の時

```math
\begin{align*}
左辺&=\mathrm{(1+x)^1}\\
右辺&=\mathrm{\sum^1_{m=0}}
\begin{pmatrix}
1\\
m
\end{pmatrix}
\mathrm{x^m}
\\
&=
\begin{pmatrix}
1\\
0
\end{pmatrix}
\mathrm{x^0}
+
\begin{pmatrix}
1\\
1
\end{pmatrix}
\mathrm{x^1}\\
&=\mathrm{1+x}
\end{align*}
```
したがって**左辺=右辺**より$\mathbf{N=1}$のときに(2.263)が成り立つことが示された。

$\mathbf{N=k}$の時に(2.263)が成り立つと仮定し$\mathbf{N=k+1}$の時にも同様に(2.263)が成り立つことを示す。

$\mathbf{N=k+1}$の時

```math
\begin{align*}
左辺&=\mathrm{(1+x)^{k+1}}\\
右辺&=\mathrm{\sum^{k+1}_{m=0}}
\begin{pmatrix}
k+1\\
m
\end{pmatrix}
\mathrm{x^m}
\\
&=\mathrm{\sum^k_{m=1}}
\begin{pmatrix}
k+1\\
m
\end{pmatrix}
\mathrm{x^m+1+x^{k+1}}\\
ここで(2.262)を使って第一項を変形する\\
&=\mathrm{\sum^k_{m=1}}\biggl\{
\begin{pmatrix}
k\\
m
\end{pmatrix}
+
\begin{pmatrix}
k\\
m-1
\end{pmatrix}
\biggr\}\mathrm{x^m+1+x^{k+1}}\\
&=\mathrm{\sum^k_{m=1}}
\begin{pmatrix}
k\\
m
\end{pmatrix}
\mathrm{x^m+1+}
\mathrm{\sum^k_{m=1}}
\begin{pmatrix}
k\\
m-1
\end{pmatrix}
\mathrm{x^m+x^{k+1}}\\
&=\mathrm{\sum^k_{m=0}}
\begin{pmatrix}
k\\
m
\end{pmatrix}
\mathrm{x^m+}
\mathrm{\sum^k_{m=1}}
\begin{pmatrix}
k\\
m-1
\end{pmatrix}
\mathrm{x^m+x^{k+1}}\\
&=\mathrm{\sum^k_{m=0}}
\begin{pmatrix}
k\\
m
\end{pmatrix}
\mathrm{x^m+x\biggl\{\sum^k_{m=0}}
\begin{pmatrix}
k\\
m
\end{pmatrix}
\mathrm{x^m-x^k\biggr\}}
\mathrm{+x^{k+1}}\\
&=\mathrm{(1+x)\sum^k_{m=0}}
\begin{pmatrix}
k\\
m
\end{pmatrix}
\mathrm{x^m}\\
(2.263)を用いると\\
&=\mathrm{(1+x)(1+x)^k}\\
&=\mathrm{(1+x)^{k+1}}
\end{align*}
```
したがって**左辺=右辺**より
$\mathbf{N}$が任意の数$\mathbf{k}$で(2.263)が成り立つと仮定したときに$\mathbf{N=k+1}$でも同様に(2.263)が成り立つ事が示された。

##(2.264)の証明
```math
\begin{align*}
\mathrm{\sum^N_{m=0}}
\begin{pmatrix}
N\\
m
\end{pmatrix}
\mathrm{\mu^m(1-\mu)^{N-m}=1}
\tag{2.264}
\end{align*}
```
誘導通り$\mathrm{(1-\mu)^N}$を$\mathbf{\sum}$の外に出してから(2.263)を用いて式変形を行う。


```math
\begin{align*}
左辺&=\mathrm{\sum^N_{m=0}}
\begin{pmatrix}
N\\
m
\end{pmatrix}
\mathrm{\mu^m(1-\mu)^{N-m}}\\
&=\mathrm{(1-\mu)^N\sum^N_{m=0}}
\begin{pmatrix}
N\\
m
\end{pmatrix}
\mathrm{\frac{\mu^m}{(1-\mu)^m}}\\
二項定理(2.263)より\\
&=\mathrm{(1-\mu)^N\Bigl(1+\frac{\mu}{(1-\mu)}\Bigr)^N}\\
&=\mathrm{(1-\mu)^N\Bigl(\frac{1}{(1-\mu)}\Bigr)^N}\\
&=1
\end{align*}
```
したがって**左辺=右辺**より(2.264)が示された。