次: 複合命題と数学的帰納法 上: 数学的帰納法 前: 数学的帰納法

変形型数学的帰納法

応用型を簡単な例題で確認しておこう．

例題 1.10       ［出典不明］

$\alpha+\beta$ ， $\alpha \beta$ が整数のとき，任意の自然数 $n$ に対して

$$\sum_{r=0}^n\alpha^{n-r}\beta ^r$$

は整数であることを示せ．

考え方     これを数学的帰納法で示そうとして $n=1$ のときの成立を確認し， $n=k$ での成立を仮定して $n=k+1$ のときの成立を示そうと計算すると

$$\begin{eqnarray*} &&\alpha^{k+1}+\alpha^k\beta+\cdots +\alpha \beta^k+\beta^{k+1... ...alpha \beta(\alpha^{k-1}+\alpha^{k-2} \beta+\cdots +\beta^{k-1}) \end{eqnarray*}$$

となる．仮定したのは $n=k$ のときなので，第二のかっこ内が整数である保証がない． このようなときは［応用型1］になる． つまり次のようにする．

解答    

数学的帰納法で示す．

1. $n=1$ のとき $$\sum_{r=0}^1\alpha^{n-r}\beta ^r =\alpha+\beta$$で成立．
   $n=2$ のとき
   
   $$\sum_{r=0}^2\alpha^{n-r}\beta ^r =\alpha^2+\alpha \beta+\beta^2=(\alpha+\beta)^2-\alpha \beta$$
   
   
   で成立．
2. $n=k,\ k+1$ で成立するとする．
   $$\begin{eqnarray*} &&\sum_{r=0}^{k+2}\alpha^{n-r}\beta ^r\\ &=&\alpha^{k+2}+\a... ...1}) -\alpha \beta(\alpha^k+\alpha^{k-1} \beta+\cdots +\beta^k) \end{eqnarray*}$$
   
   
   より $n=k+2$ のときも成立する．
3. よってすべての自然数について題意が示された． □

例題 1.11       ［00横浜国立大学改題］

数列 $\{ a_n \}$ を

$$a_0=1,\ a_n=\sum_{k=1}^n3^ka_{n-k} \quad (n=1,\ 2,\ \cdots)$$

で定める.数列 $\{ a_n \}$ の一般項 $a_n$ を求めよ.

考え方     このようになかなか解けない数列の一般項を求めたいときは， いくつかの $n$ について調べ，一般項を推測するところからはじめなければならない．

解答    

$$\begin{eqnarray*} a_1&=&3a_0=3\\ a_2&=&3a_1+3^2a_0=18\\ a_3&=&3a_2+3^2a_1+3^3a_0=108 \end{eqnarray*}$$

となるので $a_n=3\cdot6^{n-1}(n=1,\ 2,\ \cdots)$ と推測される. これを数学的帰納法で示す.

1. $n=1$ のとき， $a_1=3$ より成立.
2. $n=1,\ 2,\ \cdots,\ m$ で成立するとする. このとき
   $$\begin{eqnarray*} a_{m+1}&=&\sum_{k=1}^{m+1}3^ka_{m+1-k}\\ &=&\sum_{k=1}^m3^k... ...^{m+1} \left(\dfrac{2^m-1}{2-1}\right)+3^{m+1}\\ &=&3\cdot6^m \end{eqnarray*}$$
   
   
   よって $n=m+1$ でも成立する.
3. 以上から $n=1,\ 2,\ \cdots$ に対し $a_n=3\cdot6^{n-1}$ が示された.

ゆえに一般項は $a_n= \left\{ \begin{array}{ll} 1&(n=0)\\ 3\cdot6^{n-1}&(n\ge 1) \end{array}\right.$である． □

$a_1=3,\ a_2=18,\ a_3=108$ だからといって

$$a_n=3\cdot6^{n-1}+(n-1)(n-2)(n-3)$$

かも知れない． しかしこれはやってみれば $n=4$ で成り立たないことがわかる． 推測はもっとも妥当らしい形を推測しなければならないが， 推測すべき形は一つではないことに注意しよう．