　【SPONSORED LINK】

漸化式の基本３｜数学的帰納法の仕組みと例

2016/9/17 2019/10/30 数列

【漸化式の基本2|等差数列，等比数列の漸化式】の続きです．

「数学的帰納法」は「背理法」に並んで，高校数学で学ぶ大切な証明法の一つで，「任意の自然数 $n$ に対して，〜が成り立つことを示せ．」という問題に対して威力を発揮することが多いです．

【参考記事：背理法1|背理法の仕組みと例】
【参考記事：背理法2|背理法が有効な証明の2つのタイプと例】

「数学的帰納法」のイメージとしては「ドミノ倒し」に似ており，最初のピースを倒すと次々にピースが倒れていく感覚があります．

「数学的帰納法」は非常に大切なので，確実に押さえてください．

【SPONSORED LINK】

目次

1 数学的帰納法の仕組み
2 数学的帰納法の例
3 補足

数学的帰納法の仕組み

「任意の自然数 $n$ に対して，〜が成り立つことを示せ．」という問題に「数学的帰納法」が有効であることは冒頭に述べた通りですが，次のような2段階の論法です．

$n=1$ のときに成り立つことを示す．
「 $n=k$ のときに成り立つ」とし，それを利用して $n=k+1$ のときに成り立つことを示す．

「数学的帰納法」は「ドミノ倒し」に似ていると書きましたが，1は「最初のピースを倒す」ことに相当し，2は「( $k$ 個目のピースが倒れるか分からないけど，)もし倒れたとすると，ちゃんと $k+1$ 個目のピースも倒れる」ということに相当します．

言い換えれば，1が保証してくれるのは「最初のピースはちゃんと倒せる」ということであり，2が保証してくれるのは「 $k$ 個目が倒れれば， $k+1$ 個目のピースが倒れるようにきちんとピース並んでいる」ということですね．

ですから，1,2のどちらが欠けても，「数学的帰納法」は成り立ちません．

1が欠けていると「最初のピースが倒せない」し，2が欠けていると「 $k$ 個目が倒れても， $k+1$ 個目が倒れてくれないかもしれない」からです．

以上が「数学的帰納法」のイメージです．

1,2が証明できれば，

1より $n=1$ のときが成り立つ．
$n=1$ が成り立つから，2より $n=2$ のときが成り立つ．
$n=2$ が成り立つから，2より $n=3$ のときが成り立つ．
$n=3$ が成り立つから，2より $n=4$ のときが成り立つ．
……

と続いていくので，任意の自然数 $n$ に対して成り立つことが証明できたことになるわけです．

注意ですが，問題によっては「3以上の任意の自然数 $n$ に対して，〜を示せ．」などとなっている場合がありますが，このときは

$n=3$ のときに成り立つことを示す．
「 $n=k$ のときに成り立つ」とし，それを利用して $n=k+1$ のときに成り立つことを示す．

とすれば良いことは以上の話から分かるでしょう．

数学的帰納法の例

今から次の問題を考えます．

(1)　任意の自然数 $n$ に対して，等式 $(*):1+3+5+\dots+(2n-1)=n^2$ が成り立つことを示せ．

(2)　2以上の任意の自然数 $n$ に対して，不等式 $(*):3^n>4n$ が成り立つことを示せ．

(3)　漸化式 $a_1=1,a_{n+1}=\dfrac{a_n}{1+a_n}$ を満たす数列 $\{a_n\}$ の一般項を求めよ．

「数学的帰納法」を使いこなすにはいくらか慣れが必要ですから，実際に自分でも証明してみて下さい．

例1

任意の自然数 $n$ に対して，等式 $(*):1+3+5+\dots+(2n-1)=n^2$ が成り立つことを数学的帰納法により示す．

[1]　 $n=1$ のとき

$((*)の左辺)=1=1^2=((*)の右辺)$ となって，等式 $(*)$ が成り立つことが分かる．

[2]　「 $n=k$ のとき $(*)$ が成り立つ」とし， $n=k+1$ のとき $(*)$ が成り立つことを示す．

すなわち，「 $1+3+5+\dots+(2k-1)=k^2$ が成り立つ」とし， $1+3+5+\dots+\{2(k+1)-1\}=(k+1)^2$ が成り立つことを示す．

$1+3+5+\dots+(2k-1)=k^2$ が成り立つから，

$1+3+5+\dots+\{2(k+1)-1\}$
$=\{1+3+5+\dots+(2k-1)\}+\{2(k+1)-1\}$
$=k^2+2k+1$
$=(k+1)^2$

となって， $n=k+1$ の場合にも等式 $(*)$ が成り立つことが分かる．

[1]，[2]より示された．

例2

2以上の任意の自然数 $n$ に対して，不等式 $(*):3^n>4n$ が成り立つことを数学的帰納法により示す．

[1]　 $n=2$ のとき

$((*)の左辺)=3^2=9>8=4\times2=((*)の右辺)$ となって，不等式 $(*)$ が成り立つことが分かる．

[2]　「 $n=k$ $(k\ge2)$ のとき $(*)$ が成り立つ」とし， $n=k+1$ のとき不等式 $(*)$ が成り立つことを示す．

すなわち，「 $3^k>4k$ が成り立つ」とし， $3^{k+1}>4(k+1)$ が成り立つことを示す．

$3k>k+1$ であることに注意すると， $3^k>4k$ が成り立つから，

$3^{k+1}=3\times3^{k}>3\times4k=4\times3k>4\times(k+1)$

となって， $n=k+1$ の場合にも不等式 $(*)$ が成り立つことが分かる．

[1]，[2]より示された．

例3

$a_1=1,a_{n+1}=\dfrac{a_n}{1+a_n}$ だから，数列 $\{a_n\}$ を初項から順に求めると，

$a_1=1,$
$a_2=\dfrac{a_1}{1+a_1}=\dfrac{1}{1+1}=\dfrac{1}{2},$
$a_3=\dfrac{a_2}{1+a_2}=\dfrac{\frac{1}{2}}{1+\frac{1}{2}}=\dfrac{1}{2+1}=\dfrac{1}{3},$
$a_4=\dfrac{a_3}{1+a_3}=\dfrac{\frac{1}{3}}{1+\frac{1}{3}}=\dfrac{1}{3+1}=\dfrac{1}{4}$

となる．よって，数列 $\{a_n\}$ の一般項は $a_n=\dfrac{1}{n}$ と予想でき，これを数学的帰納法により示す．

[1]　 $n=1$ のとき

$a_1=1$ となって，予想が正しいことが分かる．

[2]　「 $n=k$ のとき予想が正しい」とし， $n=k+1$ のとき予想が正しいことが成り立つことを示す．

すなわち，「 $a_n=\dfrac{1}{n}$ が成り立つ」とし， $a_{n+1}=\dfrac{1}{n+1}$ が成り立つことを示す．

$a_n=\dfrac{1}{n}$ が成り立つから，

$a_{n+1}=\dfrac{a_n}{1+a_n}=\dfrac{\frac{1}{n}}{1+\frac{1}{n}}=\dfrac{1}{n+1}$

となって， $n=k+1$ の場合にも予想が正しいことが分かる．

[1]，[2]より，題意の一般項は $a_n=\dfrac{1}{n}$ である．

補足

例1，例2のように単に証明で「数学的帰納法」を用いることも多いですが，例3のように「〜を求めよ．」といった場合にも「予想を立てて，数学的帰納法により証明する」という手法を用いることもよくあります．

いずれにせよ，「数学的帰納法」の仕組みを理解して，証明の流れを自分で作れるようになっておかなければなりません．

「数学的帰納法」は非常に基本的で重要な証明法ですから，必ず押さえてください．