おいしい数学HOME

数学的帰納法(応用編)

数列(難関大対策) ★★★★

アイキャッチ

数学的帰納法の応用編です.

応用編は直前の仮定が複数に及ぶものを扱います.

こちらは難関大志望者向けなので,基本を学びたい方は数学的帰納法(基本編)をご覧ください.

数学的帰納法(複数の仮定が必要なもの)

数学的帰納法(隣接3項間)

自然数 $n$ に関する命題 $P(n)$ の成立を示したいときに,以下の(ⅰ),(ⅱ)が示せれば,すべての自然数 $n$ に関して $P(n)$ が成立することを示せます.

(ⅰ) $P(1)$,$P(2)$ が真である.

(ⅱ) $P(k)$,$P(k+1)$ が真ならば $P(k+2)$ も真である.

なぜなら,(ⅰ),(ⅱ)より,$P(3)$ が真であることが言え,また(ⅱ)より $P(4)$ が真であることが言えます.以後,すべての自然数 $n$ に関して $P(n)$ が真であることが言えます.


隣接3項間漸化式を作って,$a_{1}$ と $a_{2}$ を与えればすべての項が求まるのに似ています.

アイキャッチ

手前2つのドミノを使って次のドミノを倒すという,現実のドミノとは少し違った状況ですが,上の手続きを踏めばすべてのドミノが倒れます.

さらに,今までのすべての仮定を必要とするタイプもあります.

数学的帰納法(直前のすべての仮定が必要)

自然数 $n$ に関する命題 $P(n)$ の成立を示したいときに,以下の(ⅰ),(ⅱ)が示せれば,すべての自然数 $n$ に関して $P(n)$ が成立することを示せます.

(ⅰ) $P(1)$ が真である.

(ⅱ) $P(1)$,$P(2)$,$\cdots$,$P(k)$ が真ならば $P(k+1)$ も真である.

なぜなら,(ⅰ),(ⅱ)より,$P(2)$ が真であることが言え,また(ⅱ)より $P(3)$ が真であることが言えます.以後,すべての自然数 $n$ に関して $P(n)$ が真であることが言えます.


今までのすべてが成り立つとすると,次が成り立つという,条件が厳しいパターンです.

アイキャッチ

あまり入試で見かけませんが,シグマ表記が絡んだ問題が多いです.

例題と練習問題

例題

例題

実数 $x$,$y$ について,$x+y$,$xy$ がともに偶数とする.自然数 $n$ に対して $x^{n}+y^{n}$ は偶数であることを示せ.


講義

対称式は基本対称式で表せます基本編のように示そうとすると(ⅱ)のセクションで

$x^{k+1}+y^{k+1}=(x^{k}+y^{k})(x+y)-xy(x^{k-1}+y^{k-1})$

とすると,3項間の式になっていることに気がつきます.$x+y$,$xy$ はともに偶数ですが,$x$,$y$ は実数であって整数とは限らないので,$x^{k-1}+y^{k-1}$ も偶数であることを仮定すべきです


解答

$x+y=2a$,$xy=2b$ ( $a$,$b$ は整数)とおく.

(ⅰ) $n=1$ のとき $x+y$ は偶数.

$n=2$ のとき

$x^{2}+y^{2}=(x+y)^{2}-2xy=2(2a^{2}-2b)$

より $x^{n}+y^{n}$ は偶数.

(ⅱ) $n=k$,$k+1$ のとき $x^{n}+y^{n}$ は偶数である仮定すると,$x^{k+1}+y^{k+1}=2c$,$x^{k}+y^{k}=2d$ ( $c$,$d$ は整数)とおく.

$n=k+2$ のとき

 $x^{k+2}+y^{k+2}$

$=(x^{k+1}+y^{k+1})(x+y)-xy(x^{k}+y^{k})$

$=2(2ca-2bd)$

よりこのときも.$x^{n}+y^{n}$ は偶数.

(ⅰ)(ⅱ)よりすべての自然数 $n$ に関して $x^{n}+y^{n}$ は偶数.

練習問題

練習1

$p=2+\sqrt{5}$ とおき,自然数 $n=1,2,3,\cdots$ に対して

$a_{n}=p^{n}+\left(-\dfrac{1}{p}\right)^{n}$

と定める.以下の問いに答えよ.ただし設問(1)は結論のみを書けばよい.

(1) $a_{1}$,$a_{2}$ の値を求めよ.

(2) $n\geqq 2$ とする.積 $a_{1}a_{n}$ を $a_{n+1}$ と $a_{n-1}$ を用いて表せ.

(3) $a_{n}$ は自然数であることを表せ.

(4) $a_{n+1}$ と $a_{n}$ の最大公約数を求めよ.


練習2

(1) 等式 $(k+1)^{5}-k^{5}=5k^{4}+10k^{3}+10k^{2}+5k+1$ を利用して

$\displaystyle \sum_{k=1}^{n}k^{4} \ \ (n=1,2,\cdots)$

は $n$ に関する5次式として表せることを示せ.

(2) $d$ を自然数とすると

$\displaystyle \sum_{k=1}^{n}k^{d} \ \ (n=1,2,\cdots)$

は $n$ に関する $d+1$ 次式として表せることを,$d$ についての数学的帰納法を用いて示せ.

練習1の解答 出典:2017年東大理系前期

(1)

$a_{1}=p-\dfrac{1}{p}=2+\sqrt{5}-\dfrac{1}{2+\sqrt{5}}=\boldsymbol{4}$

$a_{2}=p^{2}+\dfrac{1}{p^{2}}=\left(p-\dfrac{1}{p}\right)^{2}+2=\boldsymbol{18}$


(2)

 $a_{n+1}$

$=p^{n+1}+\left(-\dfrac{1}{p}\right)^{n+1}$

$=\left\{p^{n}+\left(-\dfrac{1}{p}\right)^{n}\right\}\left\{p+\left(-\dfrac{1}{p}\right)\right\}+p^{n-1}-\left(-\dfrac{1}{p}\right)^{n}p$

$=a_{n}a_{1}+a_{n-1}$

$\therefore \ a_{1}a_{n}=a_{n+1}-a_{n-1}$


(3)

(ⅰ) $n=1$,$2$ のとき,(1)より $a_{n}$ は自然数.

(ⅱ) $n=k$,$k+1$ のとき $a_{n}$ が自然数であると成り立つと仮定する.

$n=k+2$ のとき,(2)より

 $a_{k+2}$

$=a_{k}+a_{1}a_{k+1}$

よりこのときも $a_{n}$ は自然数.

(ⅰ)(ⅱ)よりすべての自然数 $n$ に関して $a_{n}$ が自然数である.

(4)

$a_{n+1}=4a_{n}+a_{n-1}$

より,$a_{n+1}$ を $a_{n}$ で割った余りは $a_{n-1}$ なので,互除法の原理より

$\gcd(a_{n+1},a_{n})$

$=\gcd(a_{n},a_{n-1})$

$=\gcd(a_{n-1},a_{n-2})$

$\vdots$

$=\gcd(a_{2},a_{1})=\boldsymbol{2}$


練習2の解答 出典:2019聖マリアンナ医科大

(1)

 $\displaystyle \sum_{k=1}^{n}\{(k+1)^{5}-k^{5}\}$

$=(2^{5}-1^{5})+(3^{5}-2^{5})+\cdots+((n+1)^{5}-n^{5})$

$=(n+1)^{5}-1$

$=n^{5}+5n^{4}+10n^{3}+10n^{2}+5n$

一方で

 $\displaystyle \sum_{k=1}^{n}\{(k+1)^{5}-k^{5}\}$

$\displaystyle =5\sum_{k=1}^{n}k^{4}+10\sum_{k=1}^{n}k^{3}+10\sum_{k=1}^{n}k^{2}+5\sum_{k=1}^{n}k$

以上より

$\displaystyle 5\sum_{k=1}^{n}k^{4}=n^{5}+5n^{4}+10n^{3}+10n^{2}+5n-10\sum_{k=1}^{n}k^{3}-10\sum_{k=1}^{n}k^{2}-5\sum_{k=1}^{n}k$

$\displaystyle \therefore \ \sum_{k=1}^{n}k^{4}=\dfrac{1}{5}n^{5}+n^{4}+2n^{3}+2n^{2}+n-2\sum_{k=1}^{n}k^{3}-2\sum_{k=1}^{n}k^{2}-\sum_{k=1}^{n}k$

$\displaystyle \sum_{k=1}^{n}k^{3},\sum_{k=1}^{n}k^{2},\sum_{k=1}^{n}k$ はそれぞれ $n$ の4,3,2次式より,$\displaystyle \sum_{k=1}^{n}k^{4}$ は $n$ に関する5次式として表せる.


(2)

(ⅰ) $d=1$ のとき

$\displaystyle \sum_{k=1}^{n}k=\dfrac{1}{2}n(n+1)$

より $d+1$ 次式で表せる.

(ⅱ) $d\leqq m$ のとき $\displaystyle \sum_{k=1}^{n}k^{d}$ が $n$ に関する $d+1$ 次式として表せると仮定する.

 $\displaystyle \sum_{k=1}^{n}\{(k+1)^{m+2}-k^{m+2}\}$

$=(2^{m+2}-1^{m+2})+(3^{m+2}-2^{m+2})+\cdots+((n+1)^{m+2}-n^{m+2})$

$=(n+1)^{m+2}-1$

一方で

 $\displaystyle \sum_{k=1}^{n}\{(k+1)^{m+2}-k^{m+2}\}$

$\displaystyle =\sum_{k=1}^{n}\left\{_{m+2}{\rm C}_{1}\cdot k^{m+1}+_{m+2}{\rm C}_{2}\cdot k^{m}+\cdots+1\right\}$

$\displaystyle =_{m+2}{\rm C}_{1}\sum_{k=1}^{n}k^{m+1}+_{m+2}{\rm C}_{2}\sum_{k=1}^{n}k^{m}+\cdots+n$

以上より

$\displaystyle _{m+2}{\rm C}_{1}\sum_{k=1}^{n}k^{m+1}=(n+1)^{m+2}-1-\left(_{m+2}{\rm C}_{2}\sum_{k=1}^{n}k^{m}+\cdots+n\right)$

上の式の右辺は,$(n+1)^{m+2}$ が $n$ の $m+2$ 次式,$\displaystyle \left(_{m+2}{\rm C}_{2}\sum_{k=1}^{n}k^{m}+\cdots+n\right)$ が仮定より高々 $n$ の $m+1$ 次式.つまり,$\displaystyle \sum_{k=1}^{n}k^{m+1}$ は $n$ の $m+2$ 次式より,$d=m+1$ のときも $d+1$ 次式で表せる.

(ⅰ)(ⅱ)よりすべての自然数 $n$ に関して $\displaystyle \sum_{k=1}^{n}k^{d}$ が $n$ に関する $d+1$ 次式として表せる.

※ 余談ですが,次数が $d$ なのは degree の頭文字だと思います.