数学的帰納法と漸化式
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})
