数学的帰納法をわかりやすく【例題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}
となることを証明できます。
詳細は，フィボナッチ数列の8つの性質（一般項・黄金比・互いに素）の中盤，「ビネの公式の証明」の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パターンを把握しておけば，数学的帰納法の応用の幅が広がります！

数学的帰納法は素晴らしい

数学的帰納法は整数問題，数列，組み合わせ（離散数学），恒等式の証明，などなど様々な分野の証明問題に使える非常に強力な方法です。自然数 $n$ が登場する証明問題の多くは数学的帰納法で解決できます。

数学的帰納法を用いた証明と，数学的帰納法を用いずに直接証明する方法を比べると，一般的に以下のような特徴が見受けられます：

数学的帰納法：機械的な計算で証明できることが多い，発想力がいらない

直接証明する方法：発想力が必要な場合が多い，よりエレガントな解答になりやすい

もちろん，数学オリンピックの問題など，数学的帰納法を用いた上でも発想力が必要になる問題もありますが，自然数 $n$ が含まれる証明問題を見たらとりあえず，どの分野でも数学的帰納法を連想しましょう。

数学的帰納法を使えば全ての人がハゲであることを証明できます→数学的帰納法によるハゲのパラドックス

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！

まとめ