$1$, $2$, $2^2$, $\cdots$, $2^{n-1}$ を使って $1$ から $2^{n}-1$ までの自然数をすべて作れること【数学的帰納法】

証明.

便宜上, $A _n=\{1, 2, 2^2 \cdots, 2^{n-1}\}$ とする. 集合 $A_n$ の中の数をいくつか選んだ和として, $1$ から $2^{n}-1$ までの自然数を表すことができることを数学的帰納法で示す.

$n=1$ のとき, $A_1$ の要素の $1$ を用いて $1$ を表すことができる.

$n \in \mathbb{N}$ のときに, 主張が成り立つとする. つまり, $1 \leq k \leq 2^{n}-1$ を満たす自然数について, 集合 $A_n$ から重複を許さずいくつか選んだ数の和で表せると仮定する.

このとき, $1$ から $2^{n+1}-1$ までの自然数を, 集合 $A_{n+1}$ から重複を許さずいくつか選んだ数の和で表せることを示す.

帰納法の仮定から $1 \leq k \leq 2^{n}-1$ を満たす自然数については, $A_{n+1} \supset A_n$ の数の和で表すことができる. また, $2^{n} \in A_{n+1}$ より $2^{n}$ も $A_{n+1}$ の数（の和）で表すことができる. $\cdots (\ast)$

さて, $2^{n} + 1$ から $2^{n+1}-1$ までの自然数については, $1 \leq k \leq 2^{n}-1$ を用いて, $2^n + k$ と表すことができる.

$A_n\cap \{2^n\} = \emptyset$ であり, $(\ast)$ から, $k$ は $A_n$ の数の和で表すことができるので, $2^n + k$ は $A_{n+1}$ の中の数の和で表すことできる.

したがって, $n$ のときに主張が正しいと仮定すると, $n+1$ のときも主張が正しいことを示すことができた.

ゆえに, 数学的帰納法から, 任意の自然数 $n$ について, $1$ から $2^{n}-1$ までのすべての自然数は, $1$, $2$, $2^2$, $\cdots$, $2^{n-1}$ の数の中から重複を許さずいくつか選んだ数の和で表わすことができると分かる.

なお, $1$ から $2^n-1$ までの数は $2^n-1$ 個である. 一方で, 集合 $A_n$ の中から重複を許さずに数を選ぶ組み合わせは, ( $A_n$ の要素の個数が $n$ 個であるから) $2^n$ 通りである. このうち, 何も選ばない場合を除けば, $2^n-1$ 通りである.

すなわち, 作るべき数の個数と和として選ぶ数の選び方の総数が一致しているので, 和の表し方は一意的である.