分数型漸化式（逆数をとって解く）

$a_{n + 1} = \frac{a _{n}}{p a _{n} + q}$ のような分数型漸化式は、逆数をとることで解ける場合が多い。

基本パターン

$a_{n + 1} = \frac{a _{n}}{p a _{n} + q}$ の両辺の逆数をとると、

$\frac{1}{a _{n + 1}} = \frac{p a _{n} + q}{a _{n}} = p + \frac{q}{a _{n}}$

$b_{n} = \frac{1}{a _{n}}$ とおくと、

$b_{n + 1} = q b_{n} + p$

これは $b_{n + 1} = p b_{n} + q$ 型の漸化式になる。

$a_{1} = 1$ , $a_{n + 1} = \frac{a _{n}}{2 a _{n} + 1}$ を解け。

逆数をとると $\frac{1}{a _{n + 1}} = 2 + \frac{1}{a _{n}}$ 。

$b_{n} = \frac{1}{a _{n}}$ とおくと、 $b_{1} = 1$ , $b_{n + 1} = b_{n} + 2$ 。

これは等差数列で $b_{n} = 1 + 2 (n - 1) = 2 n - 1$ 。

よって $a_{n} = \frac{1}{2 n - 1}$ 。

$a_{1} = 1$ , $a_{n + 1} = \frac{a _{n}}{3 a _{n} + 2}$ を解け。

逆数をとると $\frac{1}{a _{n + 1}} = 3 + \frac{2}{a _{n}}$ 。

$b_{n} = \frac{1}{a _{n}}$ とおくと、 $b_{1} = 1$ , $b_{n + 1} = 2 b_{n} + 3$ 。

特性方程式 $x = 2 x + 3$ より $x = - 3$ 。

$b_{n + 1} + 3 = 2 (b_{n} + 3)$ なので、 ${b_{n} + 3}$ は初項 $4$ 、公比 $2$ の等比数列。

$b_{n} + 3 = 4 \cdot 2^{n - 1} = 2^{n + 1}$ より $b_{n} = 2^{n + 1} - 3$ 。

よって $a_{n} = \frac{1}{2 ^{n + 1} - 3}$ 。

$a_{n + 1} = \frac{α a _{n} + β}{γ a _{n} + δ}$ も同様に、適切な置換で線形漸化式に帰着できる場合がある。