この記事では、以下の問題を4種類の方法で証明します。
$ n $を自然数とする。$ n \geq 2 $ならば$ 2^n \geq n + 2 $であることを証明せよ。
(i) $ n = 2 $のとき、$ 2^2 = 4, 2 + 2 = 4 $であるから成立する。
(ii) $ n = k (k \geq 2) $のとき、$ 2^k \geq k + 2 $であると仮定する。$ n = k + 1 $のとき、
\begin{align*} & 2^{k + 1} \\ =& 2^k + 2^k \\ \geq& (k + 2) + (k + 2) \\ >& (k + 2) + 1\\ \end{align*}
であるから、$ n = k + 1 $のときも成立する。
以上(i)(ii)より、題意が示された。
実数$ x $に対し、$ f(x) = 2^x - (x + 2) $とする。
$ x > 2 $において
$ \frac{df}{dx} = 2^x \cdot \log{2} - 1 > 4 \log{2} - 1 > 0 $
であるから、$ f(x) $は$ x > 2 $で単調増加であり、$ f(2) = 0 $とあわせると$ f(x) > 0 $が得られる。したがって、題意が示された。
$ {(1+1)}^n $を二項定理で展開すると、
$$ {(1+1)}^n = 1 + n + \sum_{k=2}^{n} {}_n\mathrm{C}_k 1^k 1^{n-k} $$
であり、$ n \geq 2 $であれば$ \sum $には1項以上の項が存在し、かつそれらはすべて$ 1 $以上である。したがって、
$$ 2^n = {(1+1)}^n \geq 1 + n + 1 = n + 2 $$
が成り立つ。
集合$ S $を$ \{ a \in \mathbb{N} \mid 1 \leq a \leq n \} = \{ 1, 2, \cdots, n \} $とし、$ P $をその冪集合とする。
$ P $の要素の数は$ 2^n $であるから、$ P $に少なくとも$ n + 2 $個の相異なる要素が存在することを示せばよい。実際、
$$ \{\}, \{1\}, \{2\}, \cdots, \{n\}, S $$
は$ n + 2 $個の相異なる$ P $の要素であるから、題意が示された。
指数と1次式の大小比較を4種類の方法で行いましたが、私は最後の方法が一番好きです。なぜなら、数学的帰納法や二項定理といったちょっとしたテクニックが必要なはずの証明が、数えることによって終わってしまうからです。