数学的帰納法(基本編)
数列(教科書範囲) ★★
数学的帰納法の基本編です．
基本編は直前の仮定のみが必要なものを扱います．
仮定が複数に及ぶものは数学的帰納法(応用編)をご覧ください．
数学的帰納法について
数学的帰納法とは
自然数 $n$ に関する命題 $P(n)$ の成立を示したいときに，以下の(ⅰ)，(ⅱ)が示せれば，すべての自然数 $n$ に関して $P(n)$ が成立することを示せます．
(ⅰ) $P(1)$ が真である．
(ⅱ) $P(k)$ が真ならば $P(k+1)$ も真である．
なぜなら，(ⅰ)，(ⅱ)より，$P(2)$ が真であることが言え，また(ⅱ)より $P(3)$ が真であることが言えます．以後，すべての自然数 $n$ に関して $P(n)$ が真であることが言えます．
よく例えられますが，まるでドミノ倒しのようです．
すべてのドミノを倒すには上の手続きが必要です．
普通のドミノならば直前が倒れれば次のドミノは倒れますが，帰納法の応用問題では，直前の2つを使って次のドミノを倒す変則的なものもあります．それは応用編で扱います．
このページでは以下で，直前の仮定のみが必要なものを扱います．
例題と練習問題
例題
例題
$n$ を自然数とするとき，次の等式が成り立つことを数学的帰納法で証明せよ．
$1\cdot2+2\cdot3+\cdots+n(n+1)=\dfrac{1}{3}n(n+1)(n+2)$
講義
$\displaystyle 1\cdot2+2\cdot3+\cdots+n(n+1)=\sum_{k=1}^{n}k(k+1)$ なので，シグマ公式を使えば示せてしまうのですが，今回は帰納法で示すのが目的です．
以下のように，(ⅰ)，(ⅱ)のセクションに分けて示します．
解答
(ⅰ) $n=1$ のとき
$1\cdot 2=\dfrac{1}{3}\cdot 1\cdot 2\cdot 3$
より成立．
(ⅱ) $n=k$ のとき与式が成り立つと仮定すると
$\color{red}{1\cdot2+2\cdot3+\cdots+k(k+1)=\dfrac{1}{3}k(k+1)(k+2)}$
となる(上の赤い式を便宜的に仮定の式とネーミングします．次で必ず使います)．
$n=k+1$ のとき
$\color{red}{1\cdot2+2\cdot3+\cdots+k(k+1)}+(k+1)(k+2)$
$=\color{red}{\dfrac{1}{3}k(k+1)(k+2)}+(k+1)(k+2)$
$=\left(\dfrac{1}{3}k+1\right)(k+1)(k+2)$
$=\dfrac{1}{3}(k+1)(k+2)(k+3)$
よりこのときも成立．
(ⅰ)(ⅱ)よりすべての自然数 $n$ に関して与式が成立．
※ ちなみにこの等式は，連続自然数積の和で難関大受験生向けに紹介しています．
練習問題
練習1
$n$ を自然数とする．$1000^{n}+(-1)^{n-1}$ が $7$ の倍数であることを証明せよ．
練習2
$n\geqq 5$ のとき，$2^{n}>n^{2}-2n+15$ が成り立つことを示せ．
練習3
数列 $\{a_{n}\}$ の一般項を求めよ．
$a_{1}=\dfrac{1}{3}$，$a_{n+1}=\dfrac{1}{3-2a_{n}}$
練習1の解答
(ⅰ) $n=1$ のとき
$1001=7\cdot143$
より7の倍数．
(ⅱ) $n=k$ のとき，つまり $1000^{k}+(-1)^{k-1}$ が $7$ の倍数であると仮定すると
$1000^{k}+(-1)^{k-1}=7m$ ( $m$ は自然数)
$\Longleftrightarrow \ \color{red}{1000^{k}=7m-(-1)^{k-1}}$
とおける．
$n=k+1$ のとき
$1000^{k+1}+(-1)^{k}$
$=1000\cdot \color{red}{1000^{k}}+(-1)^{k}$
$=1000 \color{red}{\{7m-(-1)^{k-1}\}}+(-1)^{k}$
$=7\{1000m-143(-1)^{k-1}\}$
よりこのときも $7$ の倍数．
(ⅰ)(ⅱ)よりすべての自然数 $n$ に関して $1000^{n}+(-1)^{n-1}$ が $7$ の倍数である．
※ 合同式の練習問題に同じ問題があります．
※ 実は $11$ の倍数，$13$ の倍数でもあります．7，11，13の倍数の判定法にこの等式を使います．
練習2の解答
(ⅰ) $n=5$ のとき
$2^{5}=32>25-10+15=30$
より成立．
(ⅱ) $n=k$ $(k\geqq 5)$ のとき与式が成り立つと仮定すると
$\color{red}{2^{k}>k^{2}-2k+15}$
となる．
$n=k+1$ のとき
$2^{k+1}-\{(k+1)^{2}-2(k+1)+15\}$
$=2\cdot \color{red}{2^{k}}-(k^{2}+14)$
$> 2\color{red}{(k^{2}-2k+15)}-(k^{2}+14)$
$=k^{2}-4k+16$
$=(k-2)^{2}+12 >0$
$\therefore \ 2^{k+1}>(k+1)^{2}-2(k+1)+15$
よりこのときも成立．
(ⅰ)(ⅱ)より $n\geqq 5$ のすべての自然数 $n$ に関して与式が成立．
練習3の解答 出典：2012宮崎大改
$a_{2}=\dfrac{3}{7}$，$a_{3}=\dfrac{7}{15}$，$a_{4}=\dfrac{15}{31}$
これらより一般項を $a_{n}=\dfrac{2^{n}-1}{2^{n+1}-1} \cdots$ ①と推測し，それが正しいことを数学的帰納法で示す．
(ⅰ) $n=1$ のとき
$a_{1}=\dfrac{2-1}{4-1}=\dfrac{1}{3}$
より成立．
(ⅱ) $n=k$ のとき①が成り立つと仮定すると
$\color{red}{a_{k}=\dfrac{2^{k}-1}{2^{k+1}-1}}$
となる．
$n=k+1$ のとき
$a_{k+1}$
$=\dfrac{1}{3-2\color{red}{a_{k}}}$
$=\dfrac{1}{3-2\cdot\color{red}{\dfrac{2^{k}-1}{2^{k+1}-1}}}$
$=\dfrac{2^{k+1}-1}{3(2^{k+1}-1)-2(2^{k}-1)}$
$=\dfrac{2^{k+1}-1}{2^{k+2}-1}$
よりこのときも成立．
(ⅰ)(ⅱ)よりすべての自然数 $n$ に関して①が成立．
$\boldsymbol{a_{n}=\dfrac{2^{n}-1}{2^{n+1}-1}}$
※ 1次分数型の漸化式の解法で解けます．同じ問題が練習問題にあります．