数学的帰納法(基本編)
数列(教科書範囲) ★★

数学的帰納法の基本編です.
基本編は直前の仮定のみが必要なものを扱います.
仮定が複数に及ぶものは数学的帰納法(応用編)をご覧ください.
数学的帰納法について
数学的帰納法とは
自然数 $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次分数型の漸化式の解法で解けます.同じ問題が練習問題にあります.