いろいろな数学的帰納法
答えを推定してから数学的帰納法で証明する
答えを推定してから数学的帰納法で証明する
「証明せよ」という問題でなくても，答えを予想できれば，それを証明することによって解答になる．
いろいろな数学的帰納法～その１～
漸化式
\begin{align} \begin{cases} a_1=2\\ a_{n+1}=\dfrac{2a_n}{1+a_n} \end{cases} \ (n=1,2,\cdots)\tag{1}\label{ippankonokinoho1} \end{align}で定められる数列の一般項 $a_n$ を $n$ の式で表せ．
漸化式 $a_{n+1}=\dfrac{2a_n}{1+a_n}$ に $n=1$ を代入すると
\[a_2=\frac{2a_1}{1+a_1}=\frac{2\cdot2}{1+2}=\frac{4}{3}\]また， $n=2$ を代入すると
\[a_3=\frac{2a_2}{1+a_2}=\frac{2\cdot\dfrac{4}{3}}{1+\dfrac{4}{3}}=\frac{8}{7}\]また， $n=3$ を代入すると
\[a_4=\frac{2a_3}{1+a_3}=\frac{2\cdot\dfrac{8}{7}}{1+\dfrac{8}{7}}=\frac{16}{15}\]となるので
\[a_n=\frac{2^n}{2^n-1}\tag{2}\label{ippankonokinoho2}\]と推定できる．
以下，この推定が正しいことを数学的帰納法を用いて証明する．
- $n=1$ のとき \[a_1=\frac{2^1}{2^1-1}=2\]
- $n=m$ のとき( $m$ はある自然数とする) $\eqref{ippankonokinoho2}$ が成り立つと仮定する，つまり \[a_m=\frac{2^m}{2^m-1}\tag{3}\label{ippankonokinoho3}\]
となるので，確かに $\eqref{ippankonokinoho2}$ は成り立つ．
を仮定する．
このとき， $\eqref{ippankonokinoho2}$ で $n=m+1$ とおいた場合の成立，つまり
\[a_{m+1}=\frac{2^{m+1}}{2^{m+1}-1}\tag{4}\label{ippankonokinoho4}\]が成り立つのを以下に示す．
\begin{align} &(\eqref{ippankonokinoho4}の左辺)\\ =\ &a_{m+1}\\ =\ &\frac{2a_m}{1+a_m}\qquad\qquad\because{\eqref{ippankonokinoho1}}\\ &\uparrow\eqref{ippankonokinoho1}の漸化式は全ての自然数で成り立つ\\ =\ &\frac{2\cdot\dfrac{2^m}{2^m-1}}{1+\dfrac{2^m}{2^m-1}}\qquad\qquad\because{\eqref{ippankonokinoho3}}\\ =\ &\frac{2\cdot2^m}{2^m-1+2^m}\\ =\ &\frac{2^{m+1}}{2^{m+1}-1}\\ =\ &(\eqref{ippankonokinoho4}の右辺) \end{align}よって， $n=m$ のとき $\eqref{ippankonokinoho3}$ が成り立つと仮定すれば， $n=m+1$ の場合も $\eqref{ippankonokinoho3}$ が成り立つことがいえた．
1. 2. によって，数学的帰納法からすべての自然数 $n$ について， $\eqref{ippankonokinoho2}$ は成り立つ．
よって $\eqref{ippankonokinoho1}$ の一般項は
\[\boldsymbol{a_n=\frac{2^n}{2^n-1}}\]$n=m,m+1$ を仮定して$n=m+2$ を示す
$n=m,m+1$ を仮定して$n=m+2$ を示す
$n=m$ の場合を仮定しただけでは， $n=m+1$ の場合を証明できないときもある．このようなときは，さらに $n=m$ に加えて $n=m+1$ の場合も仮定した上で， $n=m+2$ の場合を証明してやるとよい．
いろいろな数学的帰納法～その２～
$x+\dfrac{1}{x}=t$ とするとき，すべての自然数 $n$ において
式 $x^n+\dfrac{1}{x^n}$ は $t$ の $n$ 次多項式で表される $\tag{1}\label{takosikinokinoho1}$
ことを証明せよ．
- $n=1$ のとき \[x^1+\frac{1}{x^1}=t\]
- $n=m,m+1$ のとき( $m$ はある自然数とする) $\eqref{takosikinokinoho1}$ が成り立つと仮定する，つまり \begin{align} x^m+\frac{1}{x^m}&=P_m(t)\tag{2}\label{takosikinokinoho2}\\ x^{m+1}+\frac{1}{x^{m+1}}&=P_{m+1}(t)\tag{3}\label{takosikinokinoho3} \end{align}
となり，確かに $\eqref{takosikinokinoho1}$ は成り立つ．
$n=2$ のとき
\[x^2+\frac{1}{x^2}=\left(x+\frac{1}{x}\right)^2-2=t^2-2\]となり，こちらも確かに $\eqref{takosikinokinoho1}$ は成り立つ．
$\blacktriangleleft$ $n=2$ の場合の成立を示すのは，2. の証明で必要となるからである
が成り立つと仮定する．ただし，式 $P_i(t)$ は $t$ の $i$ 次多項式を意味するものとする．
このとき， $\eqref{takosikinokinoho1}$ で $n=m+2$ とおいた場合の成立，つまり
\[x^{m+2}+\frac{1}{x^{m+2}}=P_{m+2}(t)\tag{4}\label{takosikinokinoho4}\]か成り立つことを以下示す．
\begin{align} &(\eqref{takosikinokinoho4}の左辺)\\ =\ &x^{m+2}+\frac{1}{x^{m+2}}\\ =\ &\underbrace{\left(x^{m+1}+\frac{1}{x^{m+1}}\right)}_{仮定\eqref{takosikinokinoho3}}\left(x+\frac{1}{x}\right)\\ &\qquad\qquad-\underbrace{\left(x^m+\frac{1}{x^m}\right)}_{仮定\eqref{takosikinokinoho2}}\\ =\ &t\cdot P_{m+1}(t)-P_m(t)\qquad\because\eqref{takosikinokinoho2},\eqref{takosikinokinoho3} \end{align}$\blacktriangleleft$ 仮定 $\eqref{takosikinokinoho3}$ を強引にくくり出し，つじつまあわせの部分で仮定 $\eqref{takosikinokinoho2}$ が欲しくなる
$t\cdot P_{m+1}(t)$ は $m+2$ 次多項式， $P_m(t)$ は $m$ 次多項式であり，その差 $t\cdot P_{m+1}(t)-P_m(t)$ は，必ず $m+2$ 次多項式になる．
たとえば，2次多項式 $2t^2-3t+4$ から1次多項式 $3t+2$ を引くと $2t^2-3t+4-(3t+2)=2t^2-6t+2$ となり，2次多項式が得られる．
よって， $t\cdot P_{m+1}(t)-P_m(t)$ は $t$ の $m+2$ 次多項式となるから， $P_{m+2}(t)$ とおくことができ、これは $\eqref{takosikinokinoho4}$ の右辺である．
よって， $n=m,m+1$ のとき $\eqref{takosikinokinoho1}$ が成り立つと仮定すれば， $n=m+2$ の場合も $\eqref{takosikinokinoho1}$ が成り立つことがいえた．
1. 2. によって，数学的帰納法からすべての自然数 $n$ について， $\eqref{takosikinokinoho1}$ は成り立つ．
吹き出し無題
実際に問題を解く場面は，いきなり上記のようにきれいに書き始められるようなことはないと言ってよい．実際には $n=1$ 成立を確認して， $n=m$ 成立を仮定し $n=m+1$ 成立を示そうとするのだが， $n=m+1$ 成立を示そうとしたときに，前提条件が足りないことに気が付く．そこで $n=m$ に加えて $n=m+1$ の場合も仮定した上で， $n=m+2$ の場合を証明するという発想に行き着くのである．
$n=1,2,\cdots,m$ を仮定して$n=m+1$ を示す
$n=1,2,\cdots,m$ を仮定して$n=m+1$ を示す
いろいろな数学的帰納法～その３～
次の式を満たす数列 $\{a_n\}$ の一般項 $a_n$ を $n$ の式で表せ．
\begin{align} \left(\sum_{k=1}^na_k\right)^2=\sum_{k=1}^n{a_k}^3,a_n\gt0\\ (n=1,2,3,\cdots)\\ \tag{1}\label{n=m+1no1} \end{align}この問題は「証明せよ」ではないので，まず実験から答えを予想するところからはじめる．予想が立てば，それを証明してやるのだが， $n=m+1$ の場合の成立をいうのに， $n=1,2,\cdots,m-1,m$ の場合の成立を仮定する必要がある．
$\eqref{n=m+1no1}$ に $n=1$ を代入すると
\begin{align} &\left(\sum_{k=1}^1a_k\right)^2=\sum_{k=1}^1{a_k}^3\\ \Leftrightarrow\ &{a_1}^2={a_1}^3\\ \therefore\ &a_1=1 \end{align}また $n=2$ を代入すると
\begin{align} &\left(\sum_{k=1}^2a_k\right)^2=\sum_{k=1}^2{a_k}^3\\ \Leftrightarrow\ &(a_1+a_2)^2={a_1}^3+{a_2}^3\\ \Leftrightarrow\ &(1+a_2)^2=1^3+{a_2}^3\\ \Leftrightarrow\ &{a_2}^3-{a_2}^2-2a_2=0\\ \Leftrightarrow\ &a_2(a_2+1)(a_2-2)=0\\ \therefore\ &a_2=2 \end{align}また $n=3$ を代入すると
\begin{align} &\left(\sum_{k=1}^3a_k\right)^2=\sum_{k=1}^3{a_k}^3\\ \Leftrightarrow\ &(a_1+a_2+a_3)^2={a_1}^3+{a_2}^3+{a_3}^3\\ \Leftrightarrow\ &(1+2+a_3)^2=1^3+2^3+{a_3}^3\\ \Leftrightarrow\ &{a_3}^3-{a_3}^2-6a_3=0\\ \Leftrightarrow\ &a_3(a_3+2)(a_3-3)=0\\ \therefore\ &a_3=3 \end{align}となるので
\[a_n=n\tag{2}\label{n=m+1no2}\]と推定できる．
以下，この推定が正しいことを数学的帰納法を用いて証明する．
- $n=1$ のとき \[a_1=1\]
- $n\leqq m$ ( $m$ はある自然数とする)を満たす全ての $n$ で， $\eqref{n=m+1no2}$ が成り立つと仮定する，つまり \[a_l=l\quad(1\leqq l\leqq m)\tag{3}\label{n=m+1no3}\]
となるので，確かに $\eqref{n=m+1no2}$ は成り立つ．
が成り立つと仮定する．
このとき， $\eqref{n=m+1no2}$ で $n=m+1$ とおいた場合の成立，つまり
\[a_{m+1}=m+1\tag{4}\label{n=m+1no4}\]が成り立つことを以下に示す．
$\eqref{n=m+1no1}$ より
\begin{align} &\left(\sum_{k=1}^{m+1}a_k\right)^2=\sum_{k=1}^{m+1}{a_k}^3\\ \Leftrightarrow\ &\left(\sum_{k=1}^ma_k+a_{m+1}\right)^2=\sum_{k=1}^m{a_k}^3+{a_{m+1}}^3\\ &\uparrow仮定\eqref{n=m+1no3}を組み込むための準備\\ \end{align}$l$ が $1\leqq l\leqq m$ のとき， $a_l=l$ となることを $\eqref{n=m+1no3}$ で仮定しているので $\displaystyle\sum_{k=1}^ma_k$ は
\begin{align} \sum_{k=1}^ma_k&=a_1+a_2+a_3+\cdots+a_m\\ &=1+2+3+\cdots+m\\ &=\sum_{k=1}^mk \end{align}となる．よって
\begin{align} &\left(\sum_{k=1}^ma_k+a_{m+1}\right)^2\\ &\qquad=\sum_{k=1}^m{a_k}^3+{a_{m+1}}^3\\ \Leftrightarrow\ &\left(\sum_{k=1}^mk+a_{m+1}\right)^2\\ &\qquad=\sum_{k=1}^mk^3+{a_{m+1}}^3\quad\because\eqref{n=m+1no3}\\ \Leftrightarrow\ &\left\{\frac{m(m+1)}{2}+a_{m+1}\right\}^2\\ &\qquad=\frac{m^2(m+1)^2}{4}+{a_{m+1}}^3\\ \Leftrightarrow\ &\frac{m^2(m+1)^2}{4}+m(m+1)a_{m+1}\\ &\quad+{a_{m+1}}^2=\frac{m^2(m+1)^2}{4}+{a_{m+1}}^3\\ \Leftrightarrow\ &{a_{m+1}}^3-{a_{m+1}}^2-m(m+1)a_{m+1}=0\\ \Leftrightarrow\ &a_{m+1}(a_{m+1}+m)\\ &\{a_{m+1}-(m+1)\}=0\\ \therefore\ &a_{m+1}=m+1\quad(\eqref{n=m+1no4}がいえた) \end{align}よって， $n\leqq m$ のとき $\eqref{n=m+1no2}$ が成り立つと仮定すれば， $n=m+1$ の場合も $\eqref{n=m+1no2}$ が成り立つことがいえた．
1. 2. によって，数学的帰納法からすべての自然数 $n$ について， $\eqref{n=m+1no2}$ は成り立つ．
よって $\eqref{n=m+1no1}$ を満たす一般項 $a_n$ は
\[\boldsymbol{a_n=n}\]