いわゆる分数型の漸化式の一般項

201

はじめに

分数型の漸化式というのは $a_{n + 1} = \frac{p a_{n} + q}{r a_{n} + s}$ のような形をしたものを指すらしいです．
解説サイトを見ていた時に唐突に $a_{n + 1} = a_{n} = α$ とおいて方程式を解いていたことに腹が立ち，このような手法を用いずに一般項を求める方法を紹介するとともに公式化しようと思い，こうして記事にしようと思いました．

条件

今回考える漸化式は $a_{n + 1} = \frac{p a_{n} + q}{r a_{n} + s}, a_{1} = a, r \neq 0, p s - q r \neq 0$ として， $r a_{k} + s = 0$ となる $k$ が存在すれば数列 ${a_{n}}$ は第 $k$ 項目までとします．
また， $p^{2} + s^{2} + 4 q r - 2 p s \neq 0$ とします． $= 0$ の場合は公式の見やすさのため割愛しました．よければ計算してみてください．

解法

漸化式から， $a_{n} = \frac{p_{k} a_{n - k} + q_{k}}{r_{k} a_{n - k} + s_{k}}$ となるような数列 ${p_{k}}, {q_{k}}, {r_{k}}, {s_{k}}$ が存在します．この4つの数列の一般項を求めることができれば，数列 ${a_{n}}$ の一般項は $a_{1} = a, a_{n} = \frac{p_{n - 1} a + q_{n - 1}}{r_{n - 1} a + s_{n - 1}} (n > 1)$ となります．

$\frac{p_{k} a_{n - k} + q_{k}}{r_{k} a_{n - k} + s_{k}} = \frac{p_{k} \frac{p a_{n - k - 1} + q}{r a_{n - k - 1} + s} + q_{k}}{r_{k} \frac{p a_{n - k - 1} + q}{r a_{n - k - 1} + s} + s_{k}} = \frac{(p p_{k} + r q_{k}) a_{n - k - 1} + (q p_{k} + s q_{k})}{(p r_{k} + r s_{k}) a_{n - k - 1} + (q r_{k} + s s_{k})}$

より，ある0でない実数 $m$ が存在して
$\begin{array}{r} {\begin{cases} p_{k + 1} = m (p p_{k} + r q_{k}), p_{1} = p \\ q_{k + 1} = m (q p_{k} + s q_{k}), q_{1} = q \end{cases} \end{array}$

$\begin{array}{r} {\begin{cases} r_{k + 1} = m (p r_{k} + r s_{k}), r_{1} = r \\ s_{k + 1} = m (q r_{k} + s s_{k}), s_{1} = s \end{cases} \end{array}$

となります．少し計算するとわかるように $m$ は最終的に約分されて消えるので $m = 1$ で良いでしょう．また，2つの連立漸化式を見比べたときに初項が異なるだけだとわかるので，第1式のみを考えます．

$p_{k + 2} = (p + s) p_{k + 1} + (q r - p s) p_{k}$

となります．

$p + s = u + v, q r - p s = - u v$ となるように複素数 $u, v$ をとると次のように式変形できます．
$\begin{aligned} p_{k + 2} + u p_{k + 1} & = v (p_{k + 1} + u p_{k}) \\ = v^{k} (p_{2} + u p_{1}) \\ p_{k + 1} + u p_{k} & = v^{k - 1} (p_{2} + u p_{1}) (k > 1) \end{aligned}$
同様にして，
$p_{k + 1} + v p_{k} = u^{k - 1} (p_{2} + v p_{1}) (k > 1)$
を得ます．これらは $k = 1$ のときでも成り立ちます． $u, v$ の条件から
$u = \frac{p + s + \sqrt{(p + s)^{2} - 4 (p s - q r)}}{2}, v = \frac{p + s - \sqrt{(p + s)^{2} - 4 (p s - q r)}}{2}$
とわかるので， $p^{2} + s^{2} + 4 q r - 2 p s \neq 0$ より $u \neq v$ です．
さて，
$\begin{array}{r} {\begin{cases} p_{k + 1} + u p_{k} = v^{k - 1} (p_{2} + u p_{1}) \\ p_{k + 1} + v p_{k} = u^{k - 1} (p_{2} + v p_{1}) \end{cases} \end{array}$
とわかりました．第1式から第2式を引いて両辺を $u - v$ で割ることで，以下の式を得ます．
$p_{k} = \frac{1}{u - v} (v^{k - 1} (p_{2} + u p_{1}) - u^{k - 1} (p_{2} + v p_{1}))$
また漸化式から，
$\begin{aligned} q_{k} & = \frac{1}{r} (p_{k + 1} - p p_{k}) \\ = \frac{1}{u - v} \frac{1}{r} (v^{k} (p_{2} + u p_{1}) - u^{k} (p_{2} + v p_{1}) - p v^{k - 1} (p_{2} + u p_{1}) + p u^{k - 1} (p_{2} + v p_{1})) \\ = \frac{1}{u - v} \frac{1}{r} ((v - p) v^{k - 1} (p_{2} + u p_{1}) - (u - p) u^{k - 1} (p_{2} + v p_{1})) \end{aligned}$
とわかります．ここで $p_{1} = p, p_{2} = p^{2} + q r, r_{1} = r, r_{2} = (p + s) r$ なので，それぞれ代入して
$\begin{array}{r} {\begin{cases} p_{k} = \frac{1}{u - v} (v^{k - 1} (p^{2} + q r - u p) - u^{k - 1} (p^{2} + q r - v p)) \\ q_{k} = \frac{1}{u - v} \frac{1}{r} ((v - p) v^{k - 1} (p^{2} + q r - u p) - (u - p) u^{k - 1} (p^{2} + q r - u p)) \\ r_{k} = \frac{1}{u - v} (v^{k - 1} (p + s - u) r - u^{k - 1} (p + s - v) r) \\ s_{k} = \frac{1}{u - v} ((v - p) v^{k - 1} (p + s - u) - (u - p) u^{k - 1} (p + s - v)) \end{cases} \end{array}$
となります．これで各数列の一般項を求めることができました．最後に仕上げです．
$\begin{aligned} a_{n} & = \frac{p_{n - 1} a + q_{n - 1}}{r_{n - 1} a + s_{n - 1}} \\ = \frac{(v^{n - 2} (p^{2} + q r - u p) - u^{n - 2} (p^{2} + q r - v p)) a + \frac{1}{r} ((v - p) v^{n - 2} (p^{2} + q r - u p) - (u - p) u^{n - 2} (p^{2} + q r - v p))}{(v^{n - 2} (p + s - u) r - u^{n - 2} (p + s - v) r) a + ((v - p) v^{n - 2} (p + s - u) - (u - p) u^{n - 2} (p + s - v))} \\ = \frac{1}{r} \frac{u^{n - 2} (p^{2} + q r - v p) (a r + u - p) - v^{n - 2} (p^{2} + q r - u p) (a r + v - p)}{u^{n - 2} (p + s - v) (a r + u - p) - v^{n - 2} (p + s - v) (a r + v - p)} \\ = \frac{1}{r} \frac{u^{n - 2} (p (p - v) + q r) (a r + u - p) - v^{n - 2} (p (p - u) + q r) (a r + v - p)}{u^{n - 1} (a r + u - p) - v^{n - 1} (a r + v - p)} \\ = \frac{1}{r} \frac{u^{n - 2} (p (u - s) + q r) (a r + u - p) - v^{n - 2} (p (v - s) + q r) (a r + v - p)}{u^{n - 1} (a r + u - p) - v^{n - 1} (a r + v - p)} \\ ∴ a_{n} & = \frac{1}{r} \frac{u^{n - 1} (p - v) (a r + u - p) - v^{n - 1} (p - u) (a r + v - p)}{u^{n - 1} (a r + u - p) - v^{n - 1} (a r + v - p)} (n > 1) \end{aligned}$
$n = 1$ のときを考えると，
$\begin{aligned} a_{1} & = \frac{1}{r} \frac{(p - v) (a r + u - p) - (p - u) (a r + v - p)}{(a r + u - p) - (a r + v - p)} \\ = \frac{1}{r} \frac{p (u - v) + (u - v) (a r - p)}{u - v} \\ = a \end{aligned}$
となり $n = 1$ でも成り立ちます．

以上のような一般項の求め方はとても自然で難しくありません．まとめると次のようになります．

分数型の漸化式の一般項

数列 ${a_{n}}$ が漸化式 $a_{1} = a, a_{n + 1} = \frac{p a_{n} + q}{r a_{n} + s}$ で与えられているとする．
$p + s = u + v, p s - q r = u v$ を満たすように複素数 $u, v$ をとったとき， $u \neq v$ なら数列 ${a_{n}}$ の一般項は
$a_{n} = \frac{1}{r} \frac{u^{n - 1} (p - v) (a r + u - p) - v^{n - 1} (p - u) (a r + v - p)}{u^{n - 1} (a r + u - p) - v^{n - 1} (a r + v - p)}$
である．

最後に

一般項は $u, v$ の満たす性質を用いてもう少し変形することができます．
$\begin{aligned} a_{n} & = \frac{1}{r} \frac{u^{n - 1} (p - v) (a r + u - p) - v^{n - 1} (p - u) (a r + v - p)}{u^{n - 1} (a r + u - p) - v^{n - 1} (a r + v - p)} \\ = \frac{1}{r} \frac{u^{n - 1} (a r (p - v) + (p - v) (u - p)) - v^{n - 1} (a r (p - u) + (p - u) (v - p))}{u^{n - 1} (a r + u - p) - v^{n - 1} (a r + v - p)} \\ = \frac{1}{r} \frac{u^{n - 1} (a r (p - v) + q r) - v^{n - 1} (a r (p - u) + q r)}{u^{n - 1} (a r + u - p) - v^{n - 1} (a r + v - p)} \\ = \frac{u^{n - 1} (a p - a v + q) - v^{n - 1} (a p - a u + q)}{u^{n - 1} (a r + u - p) - v^{n - 1} (a r + v - p)} \end{aligned}$

となります．この式は $r = 0$ の場合にも対応しており(実際， $r = 0, s = 1$ として $u = p, v = 1$ とおくと $a_{n} = p^{n - 1} (a + \frac{q}{p - 1}) - \frac{q}{p - 1}$ となり，これは漸化式 $a_{n + 1} = p a_{n} + q, a_{1} = a$ の一般項になっている)とても便利なのですが，式の見やすさの観点から敢えてそのままにしました．