数学的帰納法(応用編)
数列(難関大対策) ★★★★
数学的帰納法の応用編です.
応用編は直前の仮定が複数に及ぶものを扱います.
こちらは難関大志望者向けなので,基本を学びたい方は数学的帰納法(基本編)をご覧ください.
数学的帰納法(複数の仮定が必要なもの)
数学的帰納法(隣接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 の頭文字だと思います.