数学的帰納法をわかりやすく【例題3問、応用5パターン】

まとめ

更新日時 2021/03/07

数学的帰納法とは「すべての自然数 $n$ に対して○○が成り立つことを証明せよ」というタイプの問題に有効な証明方法です。

数学的帰納法

数学的帰納法について基礎から応用パターンまで分かりやすく解説します。

数学的帰納法の流れ

数学的帰納法は「すべての自然数
nnn
 に対して○○が成り立つことを証明せよ」という問題に有効です。
数学的帰納法では，以下のAとBを示します。
A. n=1n=1n=1 のとき○○は成り立つ
B. n=kn=kn=k のとき○○が成立すると仮定すると，n=k+1n=k+1n=k+1 のときも○○は成り立つ
AとBが証明できれば，
n=1n=1n=1
の場合はAより○○が成立
さらに，Bを
k=1k=1k=1
として使うと
n=2n=2n=2
でも○○が成立
さらに，Bを
k=2k=2k=2
として使うと
n=3n=3n=3
でも○○が成立
さらに…
のように，いくらでも続けられるので，すべての自然数
nnn
 に対して○○が成り立つことが分かります。
以上が，数学的帰納法を使った証明方法の流れです。ここからは，具体例を通じて数学的帰納法を理解していきましょう。

数学的帰納法の例題と練習問題

等式の証明

まずは，簡単な例題です。

例題1

すべての自然数 $n$ に対して， $1+2+\dots +n=\dfrac{1}{2}n(n+1)$ であることを，数学的帰納法で証明せよ。

AとBの2つを証明必要があります。

解答

「A. $n=1$ のとき○○は成り立つ」の証明
$n=1$ のとき
$1=\dfrac{1}{2}\times 1\times 2$ なので，目標の等式が成立します。
「B. $n=k$ のとき○○が成立すると仮定すると， $n=k+1$ のときも○○は成り立つ」の証明
$n=k$ のとき目標の等式が正しいと仮定すると $1+2+\dots +k=\dfrac{1}{2}k(k+1)$ となります。両辺に $(k+1)$ を加えると， $1+2+\dots +k+(k+1)\\ =\dfrac{1}{2}k(k+1)+(k+1)$ となります。右辺を変形すると， $\dfrac{1}{2}(k+1)(k+2) =\dfrac{1}{2}(k+1)\{(k+1)+1\}$ となります。つまり， $n=k+1$ のときにも目標の等式が正しいです。

よって，数学的帰納法により，すべての自然数 $n$ に対して目標の等式が正しいことが証明されました。

不等式の証明

練習問題1

すべての自然数 $n$ に対して $2^n\geqq 2n$ であることを証明せよ。

練習問題1の解答

解答

$n=1$ のとき，両辺は $2$ なので成立。

$n=k$ のとき， $2^k\geqq 2k$ と仮定すると，両辺に2をかけて

$2^{k+1}\geqq 4k$

あとは， $4k\geqq 2(k+1)$ なら $n=k+1$ でも目標の不等式が成立するといえる。

これは $2k\geqq 2$ と同値であり正しい。

よって，数学的帰納法により目標の不等式は示された。

→高校数学の問題集　～最短で得点力を上げるために～のT145でも不等式の有名問題と4通りの解答を紹介しています。

倍数の証明

練習問題2

すべての自然数 $n$ に対して $7^n+2n+3$ が $4$ の倍数であることを証明せよ。

練習問題2の解答

解答

$n=1$ のとき，式の値は $12$ なので $4$ の倍数。

$n=k$ のとき， $7^k+2k+3$ が $4$ の倍数と仮定すると，この値は $4N$ （ $N$ は整数）とおけて，

$7^{k+1}+2(k+1)+3\\ =7\times(4N-2k-3)+2k+2+3\\ =4\times 7N-12k-16\\ =4\times(7N-3k-4)$

となり， $n=k+1$ でも式の値は $4$ の倍数といえる。

よって，数学的帰納法により目標は示された。

数学的帰納法のパターン

1. 基本パターン数学的帰納法の基本パターンは
A. n=1n=1n=1 のとき○○は成り立つ
B. n=kn=kn=k のとき○○が成立すると仮定すると，n=k+1n=k+1n=k+1 のときも○○は成り立つ
の2つを証明することでした。
この基本パターンで証明できる主張はたくさんあります（難しいものも多いです）。
定理1
すべての自然数
nnn
 について，連続する
nnn
 個の整数の積は
n!n!n!
 の倍数である
定理1の数学的帰納法による証明は連続するn個の整数の積と二項係数の3番目の証明です。
他にも，数学的帰納法の基本パターンは
包除原理の2通りの証明の2番目の証明，イェンゼンの不等式の3通りの証明の1番目の証明，ライプニッツの公式の証明と二項定理などに登場します。
2. 一つ前だけでなく二つ前も仮定するパターンここからは，数学的帰納法の応用パターンです。
n=1,2n=1, 2n=1,2
 の場合を証明した後，n=k,k+1n=k,k+1n=k,k+1
 の場合を仮定して，n=k+2n=k+2n=k+2
 の場合にも成り立つことを証明するパターンです。
例えば，1,1,2,3,5,8,13,…1,1,2,3,5,8,13,\dots1,1,2,3,5,8,13,…
 のように続く有名な数列「フィボナッチ数列」の一般項が
15{(1+52)n−(1−52)n}\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}5​1​{(21+5​​)n−(21−5​​)n}
となることを証明できます。
詳細は，フィボナッチ数列の7つの性質（一般項・黄金比・互いに素）の中盤，「ビネの公式の証明」の2つめで解説しています。
さらに，3つ以上仮定することもあります。
3. 前の項を全て仮定するパターンさきほどのパターン2をさらに一般化したもので，数学オリンピックの離散数学などの難問ではこのパターンが多いです。
n=1n=1n=1
 の場合を証明した後，n≤k−1n\leq k-1n≤k−1
 を満たす全ての自然数
nnn
 に対して成り立つと仮定して，n=kn=kn=k
 の場合にも成り立つことを証明します。
例
オイラーグラフの定理（一筆書きできる条件）とその証明
4. 後ろ向き帰納法（無限降下法）n=kn=kn=k
 のときを仮定して
n=k−1n=k-1n=k−1
 の場合を証明します。背理法と組み合わせて使うことが多く，無限降下法と呼ばれます。
例
フィボナッチ数列の一般項と数学的帰納法の性質1の証明
例
無限降下法の整数問題への応用例
5. 多変数の数学的帰納法レアなケースです。複数の自然数のペア
(m,n)(m, n)(m,n)
 全てに関して成立すること示します。原点から離れる方向にドミノ倒しをしていくイメージです。
例
ヴァンデルモンドの畳み込みの証明
以上の5パターンを把握しておけば，数学的帰納法の応用の幅が広がります！