基礎知識

【数列】数学的帰納法の意味と証明の具体例

2019.04.03

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

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

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

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

1 数学的帰納法とは
2 数学的帰納法を理解する
3 数学的帰納法を用いた証明の例題
4 数学的帰納法の説明のおわりに

数学的帰納法とは

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

自然数 $n$ に関する命題 $P(n)$ について

$n=1$ のとき命題が真であることを確認する。
$n=k$ のとき命題が真であることを仮定する。
$n=k+1$ のとき命題が真であることを確認する。

1〜3より、全ての自然数 $n$ について命題は真であると結論づける。

数学的帰納法を理解する

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

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

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

$n=1$ のとき、P(1)の真偽を判定し、その結果は真であった。
$n=2$ のとき、P(2)の真偽を判定し、その結果は真であった。
$n=3$ のとき、P(3)の真偽を判定し、その結果は真であった。

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

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

$n=4$ のとき、P(4)の真偽を判定し、その結果は真であった。

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

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

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

そこで、

$n=k$ のときの命題 $P(k)$ が真であることを仮定します。

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

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

マスマスターの思考回路

命題 $P(k)$ の真偽を真であると仮定すること自体には問題ありません。
命題 $P(k)$ が真であると仮定することによって矛盾が発生しなければその仮定は事実になるからです。

仮定を行ったことによって矛盾が発生すれば、背理法により命題 $P(n)$ が全ての自然数については成り立たないと結論づければよいでしょう。

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

マスマスターの思考回路

今は数学的帰納法の概要の解説ですので、「 $n=k$ のときの命題 $P(k)$ が真であることを仮定することによって、 $n=k+1$ のときの命題 $P(k+1)$ の真偽を判定することができるようになる」ことについては理解するのが難しいかと思います。

後の具体例でこのことは理解できるようになりますので、このまま読み進めてください。

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

$n=k+1$ のとき、 $P(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(1)$ が真であれば、 $P(2)$ も真
$P(2)$ が真であるから、 $P(3)$ も真
$P(3)$ が真であるから、 $P(4)$ も真
$P(4)$ が真であるから、 $P(5)$ も真

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

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

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

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

例題 : すべての事前数 $n$ について、 $2^{n+1}+3^{2n-1}$ は $7$ の倍数であることを証明せよ。

マスマスターの思考回路

まず、 $n=1$ のときの確認を行います。

$n=1$ のとき、

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

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

マスマスターの思考回路

次に $n=k$ のとき、命題が成立することを仮定しましょう。

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

(1) $\begin{eqnarray*}2^{k+1}+3^{2k-1} &=& 7m \\\\\end{eqnarray*}$

と表すことができます。

マスマスターの思考回路

次に $n=k+1$ のとき、命題が成立することを確認しましょう。

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

$\begin{eqnarray*}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{eqnarray*}$

ここで、(1)式より、

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

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

$\begin{eqnarray*}&=& 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{eqnarray*}$

$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$ についての証明を行う場合には、数学的帰納法を使うことを真っ先に考えると良いと思います。

【数列】数列のまとめ

基礎知識

数列

教科別目次

数I 数A 数II 数B 数III

プロフィール

-このサイトの記事を書いている人-

某国立大工学部卒のwebエンジニアです。
学生時代に塾講師として勤務していた際、生徒さんから「解説を聞けば理解できるけど、なぜその解き方を思いつくのかがわからない」という声を多くいただきました。
授業という限られた時間の中ではこの声に応えることは難しく、ある程度の理解度までに留めつつ、繰り返しの復習で覚えてもらうという方法を採らざるを得ないこともありました。
本ブログでは「数学の問題を解くための思考回路」に重点を置いています。
それらを通じて自らの力で問題を解決する力が身につくお手伝いができれば幸いです。

お問い合わせ

>> お問い合わせ

>> プライバシーポリシー

検索

この記事の目次

ピックアップ

【基礎知識】乃木坂46の「いつかできるから今日できる」を数学的命題として解釈する

命題

基礎知識

正しい暗記数学の方法と暗記数学の限界

勉強の前に

東大数学は難しくない？意外なほど簡単に解ける東京大学数学指南

勉強の前に

【大学入試／おすすめ】数学の参考書は青チャート1冊だけで良い！その理由は？…

勉強の前に

【数学とプログラミングの関係】高校でのプログラミング必修化の懸念

勉強の前に

【複素数平面】複素数の偏角の求め方

複素数平面

基礎知識

整数の割り算と商および余り

整数

基礎知識

【整数】約数と倍数・倍数の判定方法

整数

基礎知識

【整数】最大公約数と最小公倍数

整数

基礎知識

素因数分解の方法

整数

基礎知識

数列の和と一般項

数列

基礎知識

【数列】数学的帰納法の意味と証明の具体例

数学的帰納法とは

数学的帰納法を理解する

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

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

教科別目次

プロフィール

お問い合わせ

検索

カテゴリー

タグ

この記事の目次

ピックアップ

関連記事

サイドメニュー