基礎知識

ここでは、数学的帰納法について例題を交えて説明していきます。

数学的帰納法は、「すべての自然数に対して成立する式を証明する」ような場合にとても有用な証明手法になります。

また、漸化式から数列の一般項を予想して、それを数学的帰納法を用いて証明することによって数列の一般項を決定するという方法も有名です。

数学的帰納法を用いて証明が行えそうな問題の場合は、多くの場合、数学的帰納法を用いる方法が最も簡単な証明方法になりますので積極的に使っていきましょう。

数学的帰納法とは

数学的帰納法とは、下のような手順による証明方法のことをいいます。

数学的帰納法を理解する

数学的帰納法について、言葉だけの説明ではイメージがわきませんよね？

少し、具体的に考えてみましょう。

命題$P(n)$について、

このとき、$n$が全ての自然数について成り立つような気がしますよね？
しかし当然ですが、この時点では$n=4$のときの命題$P(4)$の真偽を実際に確認にしたわけではありませんので、命題$P(4)$の真偽はわかりません。

では、引き続き$P(4)$を調べてみましょう。

ますます、$n$が全ての自然数について成り立つような気がしますよね？

では、$P(5)$は真でしょうか？
それは確認していないのでわかりません。

つまり、$n$の値を1つずつ変えて確認していったところで、自然数は無限に存在しますから、全ての自然数について$P(n)$の真偽を確認することは事実上できないわけです。

そこで、

$n=k$というのは、$n$の値を適当な$k$という一定の値に固定している状況になります。

これまで、$n = 1, 2, 3, 4$の場合は真であることを確認してきましたが、$k$の値は$1, 2, 3, 4$のいずれかである保証がありません。
よって、命題$P(k)$の真偽は不明ですが、真であるものと仮定してしまいます。

$n=k$のときの命題$P(k)$が真であることを仮定したことによって、それは矛盾が発生するまでは事実になります。
この事実を用いて、$n=k+1$のときの命題$P(k+1)$の真偽を判定することができるようになります。

$n=k$のときの命題$P(k)$が真であることを仮定した状況で、$n=k+1$の場合を考えます。

このとき、$P(k)$と$P(k+1)$が真であることになり、このことは非常に重要な意味を持ちます。

ここまでで、$P(4)$が真であることは確認済みで、$P(5)$の真偽は不明という状況になっていますが、$P(k)$と$P(k+1)$が真であることを用いると、$P(5)$が真であることがわかります。

つまり、次に調べるべき命題（$n$の値を1足した命題）は真であるということがわかる状況になっているのです。

$P(5)$が真であることは$P(4)$が真であることを元に得られていますので、$P(4)$が真であることは事前に確認済みでなければならないことになりまが、実際には$P(1)$が真であることだけ確認していれば$P(5)$が真であることを言うには十分です。

つまり、

というように、連鎖的に命題$P(n)$が真であることがわかるからです。

このような連鎖は無限に続きますので、全ての自然数$n$を代入して真偽を確認しなくても、全ての自然数$n$について命題$P(n)$が真であると結論づけることができるということになります。

数学的帰納法を用いた証明の例題

数学的帰納法について理解できましたか？
この時点で十分に理解できていなくても問題ありません。
具体例を通して理解を深めていきましょう。

$n=1$のとき、

$$\begin{array}{rcl} 2^{n+1}+3^{2n-1}　&=& 2^{1+1}+3^{2\cdot 1-1} \\\\ &=& 2^{2}+3^{1} \\\\ &=& 4+3 \\\\ &=& 7 \end{array}$$

より、$2^{n+1}+3^{2n-1}$は$7$の倍数になります。

$n=k$のとき、$2^{n+1}+3^{2n-1}$は$7$の倍数であることを仮定すると、整数$m$を用いて、

$$\begin{align} 2^{k+1}+3^{2k-1} &=& 7m \end{align}$$

と表すことができます。

$n=k+1$のとき、$2^{n+1}+3^{2n-1}$は、

$$\begin{array}{rcl} 2^{n+1}+3^{2n-1}　&=& 2^{(k+1)+1}+3^{2(k+1)-1} \\\\ &=& 2^{k+2}+3^{2k+1} \\\\ &=& 2 \cdot 2^{k+1}+3^{2k+1} \end{array}$$

ここで、(1)式より、

$$\begin{array}{rcl} 2^{k+1} &=& 7m – 3^{2k-1} \end{array}$$

であるから、指数法則を用いて計算を行うと、

$$\begin{array}{rcl} &=& 2 \cdot (7m – 3^{2k-1})　+　3^{2k+1} \\\\ &=& 14m – 2 \cdot 3^{2k-1}　+　3^2 \cdot 3^{2k-1} \\\\ &=& 14m – 2 \cdot 3^{2k-1}　+　9 \cdot 3^{2k-1} \\\\ &=& 14m 　+　7 \cdot 3^{2k-1} \\\\ &=& 7(2m 　+　3^{2k-1}) \end{array}$$

$2m 　+　3^{2k-1}$は整数であるから、$7(2m 　+　3^{2k-1})$も$7$の倍数となります。
つまり、$n=k+1$のときも$2^{n+1}+3^{2n-1}$は$7$の倍数になります。

以上により、すべての自然数$n$について、$2^{n+1}+3^{2n-1}$は$7$の倍数であることが証明されました。

数学的帰納法の説明のおわりに

いかがでしたか？

数学的帰納法はその根本的な考え方は理解しにくく、とっつきにくいものではあります。
しかし、実際の証明の流れについては、慣れてしまえばそれほど難しいものではありません。

数学的帰納法は証明を機械的に進めることができるという点で、とても使い勝手がよく重宝します。

すべての自然数$n$についての証明を行う場合には、数学的帰納法を使うことを真っ先に考えると良いと思います。

【数列】数列のまとめ