漸化式と数学的帰納法の練習問題

基本の 3 つの型

• 等差型 $a_{n+1} = a_n + d$：公差 $d$ の等差数列なので $a_n = a_1 + (n-1)d$。
• 等比型 $a_{n+1} = ra_n$：公比 $r$ の等比数列なので $a_n = a_1r^{n-1}$。
• 階差型 $a_{n+1} = a_n + f(n)$：$n \geqq 2$ のとき $a_n = a_1 + \sum_{k=1}^{n-1} f(k)$。最後に $n = 1$ のときを確かめます。

a_{n+1} = pa_n + q 型

$\alpha = p\alpha + q$ を満たす $\alpha$（特性方程式の解）を求めると、漸化式は

と変形できます。数列 $\{a_n - \alpha\}$ は公比 $p$ の等比数列なので、$a_n - \alpha = (a_1 - \alpha)p^{n-1}$ です。

例：$a_1 = 3$, $a_{n+1} = 2a_n - 1$ のとき、$\alpha = 2\alpha - 1$ より $\alpha = 1$。$a_n - 1 = 2 \cdot 2^{n-1}$ なので $a_n = 2^n + 1$ です。

和 S_n と一般項 a_n

$S_n = 2a_n + n$ のように $S_n$ と $a_n$ の関係式が与えられたときは、$n$ を $n+1$ にした式との差をとると $a_{n+1}$ と $a_n$ の漸化式になります。

いろいろな漸化式と数学的帰納法

• $a_{n+1} = \dfrac{a_n}{pa_n + 1}$ 型：両辺の逆数をとると、$\left\{\dfrac{1}{a_n}\right\}$ が等差数列になります。
• $a_{n+1} = pa_n + q^n$ 型：両辺を $q^{n+1}$ で割り、$b_n = \dfrac{a_n}{q^n}$ とおきます。
• $a_{n+2} = (\alpha + \beta)a_{n+1} - \alpha\beta a_n$ 型（3 項間）：$a_{n+2} - \alpha a_{n+1} = \beta(a_{n+1} - \alpha a_n)$ のように 2 通りに変形します。