数学的帰納法と漸化式
1.数学的帰納法
自然数について述べられてた命題についての証明に用いられる。
— 証明法 —
命題P(n)について
① \( n=1 \) の時、P(n)が成り立つ。
② \( n=k \) の時、P(n)が成り立つと仮定すれば、 \( n=k+1 \) の時も、P(n)が成り立つ。
この二つを示せれば、命題が自然数 \( n \) について成り立つことが言える。
① \( \frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3\cdot 4} + \cdots + \frac{1}{n\cdot (n+1)} = \frac{n}{n+1} \) が自然数 n について成り立つことを数学的帰納法により証明せよ。
② 6以上の全ての自然数 n に対して、 \( 2^n > (n+1)^2 \) が成り立つことを数学的帰納法により証明せよ。
例題①).
(1). \( n=1 \) の時、
\( 左辺 = \frac{1}{1\cdot 2} = \frac{1}{2} \)
\( 右辺 = \frac{1}{1+1} = \frac{1}{2} \)
となり、成り立つことが分かる。
(2). \( n=k \) の時、与式が成り立つと仮定すると
\( n=k+1 \) の時、
\( 左辺 = \frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3\cdot 4} + \cdots + \frac{1}{k\cdot (k+1)} + \frac{1}{(k+1)\cdot (k+2)} \)
\( \quad \quad = \frac{k}{k+1} + \frac{1}{(k+1)\cdot (k+2)} \)
\( \quad \quad = \frac{1}{k+1} ( k + \frac{1}{k+2} ) \)
\( \quad \quad = \frac{1}{k+1} \frac{(k+1)^2}{k+2} \)
\( \quad \quad = \frac{k+1}{k+2} = 右辺 \)
よって、 \( n=k+1 \) の時でも、成り立つ
ゆえに(1),(2)より、数学的帰納法により成り立つことがわかる。
例題②).
(1). \( n=6 \) の時、
\( 左辺 = 2^6 = 64 \)
\( 右辺 = (6+1)^2 = 49 \)
であり、与式が成り立つ
(2). \( n=k\quad (k \ge 6) \) の時、与式が成り立つと仮定すると
\( n=k+1 \) の時、
\( 左辺 = 2^{k+1} = 2\cdot 2^k > 2\cdot(k+1)^2 \)
次に、 \( 2\cdot(k+1)^2 \quad と \quad (k+2)^2 \) の差を調べると
\( ( 2\cdot(k+1)^2 ) – (k+2)^2 = k^2 -2 >0 \quad (∵k \ge 6) \)
よって
\( 2^{k+1} > 2\cdot(k+1)^2 > (k+2)^2 \)
よって、 \( n=k+1 \) の時でも、成り立つ
ゆえに(1),(2)より、数学的帰納法により成り立つことがわかる。
2.漸化式
各項がそれ以前の項の関数として定まる数列の等式である。
— 漸化式の例 —
① 階差数列の形 \( a_{n+1} – a_n = f(n) \)
\begin{eqnarray}
a_{n} = a_1 +\sum_{k=1}^{n-1} f(k) \quad (n \ge 2)
\end{eqnarray}
② \( a_{n+1} = f(n)a_n \)
\begin{eqnarray}
a_n = f(n-1)f(n-2) \cdots f(2)f(1)a_1
\end{eqnarray}
③ \( a_{n+1} = p a_n + q \quad (n=1,2,3,\cdots \cdots , ; p \neq 1,\quad q \neq 0 ) \)
\( \alpha = p \alpha + q \) となる \( \alpha \) をとり、各辺を引くと
\( a_{n+1} – \alpha = p(a_n – \alpha) \)
と表せられるので、数列{ \( a_n – \alpha \) } は
\( 公比p,\quad 初項(a_1 – \alpha) \) の等比数列となる
ゆえに、
\( a_n -\alpha = (a_1 -\alpha)p^{n-1} \)
④ \( a_{n+1} = pa_n + g(n) \quad (p \neq 0 ) \)
両辺を \( p^{n+1} \) で割ると、
\( \frac{a_{n+1}}{p^{n+1}} – \frac{a_n}{p^n} = \frac{g(n)}{p^{n+1}} \)
ここで、 \( c_n = \frac{a_n}{p^n} \) , \( f(n) = \frac{g(n)}{p^{n+1}} \) と置くと
\( c_{n+1} – c_n = f(n) \) となり①の方法で解ける。
① \( a_1 = 1,\quad a_{n+1}=\frac{n}{n+1} a_n \) の数列 \( a_n \) を求めよ。
② \( a_1 = 1,\quad a_{n+1} = 3a_n + 2 \) の数列 \( a_n \) を求めよ。
③ \( a_1 = 1,\quad a_{n+1} = 3a_n + 3^{n+1} \) の数列 \( a_n \) を求めよ。
例題①).
\( a_n = \frac{n-1}{n}a_{n-1} \)
\( a_n = \frac{n-1}{n} \frac{n-2}{n-1} a_{n-2} \)
\( a_n = \frac{n-1}{n} \frac{n-2}{n-1}\frac{n-3}{n-2} \cdots \cdots \frac{1}{2} a_1 = \frac{1}{n} \)
例題②).
\( \alpha = 3\alpha +2 \) を与式から引くと、
\( a_{n+1} – \alpha = 3(a_n – \alpha) \)
\( a_{n+1} = 3a_n – 2\alpha \) となり、与式と比較して、 \( \alpha = -1 \)
つまり、
\( a_{n+1} +1 = 3(a_n +1) \)
となり、 \( \{ a_n +1 \} \) の数列の初項は 2 、公比は 3 とわかるので、
\( a_n +1 = 2\cdot 3^{n-1} \)
∴ \( a_n = 2\cdot 3^{n-1} -1 \)
例題③).
両辺を \( 3^{n+1} \) で割り、 \( c_n = \frac{a_n}{3^n} \) と置くと
\( c_{n+1} = c_n + 1 \)
つまり、
\( c_n = c_1 + \sum_{k=1}^{n-1} 1 \)
\( c_n = \frac{1_1}{3} + (n-1) = n-\frac{2}{3} \)
よって、 \( c_n = \frac{a_n}{3^n} \) なので、
\( a_n = 3^n (n-\frac{2}{3}) \)
