$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$ までの自然数が表せることを数学的帰納法で示す。

$2^1 - 1 = 1$ である。$A_1 = \{1\}$ より, 要素 $1$ を選ぶことで $1$ を表すことができ, 主張は成り立つ。

$1 \leqq k \leqq 2^n - 1$ を満たすすべての自然数 $k$ が, $A_n$ の要素の和で表せると仮定する。

$1$ から $2^{n+1}-1$ までの数を, 以下の3つの範囲に分けて考える。

• (i) $1 \leqq k \leqq 2^n - 1$ のとき：
  帰納法の仮定より, $A_n$（すなわち $A_{n+1}$ の部分集合）の要素の和で表せる。
• (ii) $k = 2^n$ のとき：
  $2^n \in A_{n+1}$ であるため, 単独の要素として表せる。
• (iii) $2^n + 1 \leqq k \leqq 2^{n+1} - 1$ のとき：
  この範囲の数は $2^n + m$ （ただし $1 \leqq m \leqq 2^n - 1$）と書ける。仮定より $m$ は $A_n$ の要素の和で表せ, かつ $2^n \notin A_n$ であるため, 重複なく $A_{n+1}$ の要素の和として表せる。

よって, $n+1$ のときも主張は正しい。

$A_n$ の各要素について「選ぶ・選ばない」の2通りがあるため, 選び方の総数は $2^n$ 通りである。ここから「何も選ばない（和が0）」場合を除くと, 有効な和の作り方は全部で $2^n - 1$ 通りとなる。

表すべき自然数の個数（$1$ から $2^n-1$ まで）も $2^n-1$ 個であり, 選び方の総数と一致する。すべての自然数が少なくとも1通りで表せることは既に示したため, 各自然数に対する選び方は一意的である。