おいしい数学HOME

数学的帰納法(基本編)

数列(教科書範囲) ★★


アイキャッチ

数学的帰納法の基本編です.

基本編は直前の仮定のみが必要なものを扱います.

仮定が複数に及ぶものは数学的帰納法(応用編)をご覧ください.



数学的帰納法について

ポイント

数学的帰納法とは

自然数 $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次分数型の漸化式の解法で解けます.同じ問題が練習問題にあります.