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

変形型数学的帰納法

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


例題 1.10       [出典不明]

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

\begin{displaymath}
\sum_{r=0}^n\alpha^{n-r}\beta ^r
\end{displaymath}

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

考え方     これを数学的帰納法で示そうとして $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$ のとき $\displaystyle \sum_{r=0}^1\alpha^{n-r}\beta ^r
=\alpha+\beta$で成立.
    $n=2$ のとき

    \begin{displaymath}
\sum_{r=0}^2\alpha^{n-r}\beta ^r
=\alpha^2+\alpha \beta+\beta^2=(\alpha+\beta)^2-\alpha \beta
\end{displaymath}

    で成立.
  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 \}$

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

で定める.数列 $\{ 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$ だからといって

\begin{displaymath}
a_n=3\cdot6^{n-1}+(n-1)(n-2)(n-3)
\end{displaymath}

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



Aozora Gakuen