【標準】途中から始まる数学的帰納法

数学的帰納法は、1から始まる場合以外でも使えます。ここでは、途中から始まる場合を見ていきます。

途中から始まる数学的帰納法

例題
$n$ を4以上の自然数とする。このとき、\[ n! \gt 2^n \]が成り立つことを示しなさい。

【基本】数学的帰納法などで見てきた通り、数学的帰納法は

  • $n=1$ のときに成り立つ
  • $n=k$ のときに成り立てば、 $n=k+1$ のときも成り立つ

という2つのステップを示すことで、どんな自然数でも成り立つことを示す、というものでしたね。

この例題では、「4以上の自然数」となっており、1から出発していません。今までと違うケースですが、こういう場合でも数学的帰納法を使って示すことができます。この場合、変えるところはステップ1の部分です。今の例題ならば「 $n=4$ のときに成り立つ」を示すことになります。

$n=4$ の場合が示せれば、これと2つ目のステップから $n=5$ の場合が成り立つことがわかり、さらに2つ目のステップから $n=6$ の場合もわかり、…というように、4以上のすべての自然数について成り立つことがわかります。

つまり、途中から始まる場合は、スタートの位置を変えるだけで、あとは同じようなドミノ倒しが使える、ということです。

それでは、示してみましょう。

(i) $n=4$ の場合、 $4!=24$ で、 $2^4=16$ なので、 $n! \gt 2^n$ が成り立つ。

(ii) $n=k$ のときに $k! \gt 2^k$ が成り立つとします( $k$ は4以上の自然数)。このときに、 $(k+1)! \gt 2^{k+1}$ が成り立つことを示します。

左辺は $(k+1)\cdot k!$ と変形できます。こうすると、仮定が使えますね。
\begin{eqnarray}
(k+1)!
&=&
(k+1)\cdot k! \\[5pt] &\gt&
(k+1)\cdot 2^k \\[5pt] &\gt&
2\cdot 2^k \\[5pt] &=&
2^{k+1} \\[5pt] \end{eqnarray}となります。2つ目の不等号は $k\geqq 4$ だから成り立つことですね。この式から、 $(k+1)! \gt 2^{k+1}$ が成り立つことが示せました。

(i)(ii)より、数学的帰納法から、4以上の自然数 n について、 $n! \gt 2^n$ が成り立つことが示せました。

4からスタートしたので、4以上の場合が示せます。今の場合は、 $n=1,2,3$ の場合には上の不等式は成り立たないので、4からスタートするしかありません。

他の問題で、もし2からスタートすれば、2以上の場合が示せます。スタートする場所によって、示せる範囲が異なります。

直接示す方法

上の例題であれば、数学的帰納法を使わずに示すこともできます。

$n\geqq 4$ のとき、
\begin{eqnarray}
n!
&=&
n(n-1)(n-2)\cdots4\cdot3\cdot2\cdot1 \\[5pt] &\geqq&
2\cdot2\cdot2\cdots2\cdot4\cdot3\cdot2\cdot1 \\[5pt] &=&
2^{n-4}\cdot4\cdot3\cdot2\cdot1 \\[5pt] &\gt&
2^{n-4}\cdot2^2\cdot2\cdot2\cdot1 \\[5pt] &=&
2^n
\end{eqnarray}となります。つまり、 $5$ から $n$ までの部分は(あれば)、それぞれ $2$ 以上だということ、また、 $1$ から $4$ までの部分の積は $2^4$ より大きいこと、この2つから、 $n!$ は $2^n$ より大きくなる、ということです。積をパーツに分けて評価しています。

おわりに

ここでは、 $1$ 以外の数字から始まる数学的帰納法について見てきました。スタートが変わっても、次に進むステップが変わらないので、本質的には違いはありません。4からスタートすれば、4以上の場合が示せます。理屈が分かっていれば、何をすべきかは自然と理解できるでしょう。