解答
\(|X|=n\)のとき、\(|Pow(X)|=2\,^n\)である。
証明
数学的帰納法を用いる。
(i) \(n=1\)、すなわち\(|X|:=|{a}|=1\)のとき
\[
\begin{align}
Pow(X) &= |{\emptyset, {a}}| \\
&= 2\,^1
\end{align}
\]
(ii) \(n=k\)、すなわち\(|X|:=|{b_{1}, b_{2}, b_{3}, \ldots, b_{k-1}, b_{k}}|\)のとき
\(
Pow(X) = 1+{}_k \mathrm{ C }_1+{}_k \mathrm{ C }_2+\ldots+{}_k\mathrm{ C }_k= 2\,^k
\)であると仮定すると、
\(n=k+1\)のとき
\[
\begin{align}
Pow(X) &= 2\,^k+(1+{}_k \mathrm{ C }_1+{}_k \mathrm{ C }_2+\ldots+{}_k\mathrm{ C }_k)\\
&= 2\,^k+2\,^k\\
&= 2\,^k\cdot 2\\
&= 2\,^{k+1}\\
\end{align}
\]
である。よって、
\(|X|=n\)のとき、\(|Pow(X)|=2\,^n\)
が成り立つ。
