連立漸化式

2つの数列が互いに絡み合った漸化式を連立漸化式という。

${a_{n + 1} = p a_{n} + q b_{n} b_{n + 1} = r a_{n} + s b_{n}$

解法1：和と差を作る

$a_{n} + b_{n}$ や $a_{n} - b_{n}$ を作ると、単独の漸化式になる場合がある。

$a_{1} = 1$ , $b_{1} = 0$ , $a_{n + 1} = 2 a_{n} + b_{n}$ , $b_{n + 1} = a_{n} + 2 b_{n}$ を解け。

和と差を作ると、

$a_{n + 1} + b_{n + 1} = 3 (a_{n} + b_{n})$ より $a_{n} + b_{n} = 3^{n}$

$a_{n + 1} - b_{n + 1} = a_{n} - b_{n}$ より $a_{n} - b_{n} = 1$

連立して $a_{n} = \frac{3 ^{n} + 1}{2}$ , $b_{n} = \frac{3 ^{n} - 1}{2}$ 。

一方の数列を消去して、他方だけの漸化式を導く。

$a_{1} = 1$ , $b_{1} = 2$ , $a_{n + 1} = 3 a_{n} - b_{n}$ , $b_{n + 1} = a_{n} + b_{n}$ を解け。

2つ目の式より $a_{n} = b_{n + 1} - b_{n}$ 。1つ目の式に代入すると、

$b_{n + 2} - b_{n + 1} = 3 (b_{n + 1} - b_{n}) - b_{n}$

整理して $b_{n + 2} - 4 b_{n + 1} + 4 b_{n} = 0$ 。

特性方程式 $(x - 2)^{2} = 0$ より重解 $x = 2$ 。

$b_{n} = (A n + B) \cdot 2^{n}$ 。 $b_{1} = 2$ , $b_{2} = a_{1} + b_{1} = 3$ より $A = - \frac{1}{4}$ , $B = \frac{5}{4}$ 。

$b_{n} = \frac{5 - n}{4} \cdot 2^{n} = (5 - n) \cdot 2^{n - 2}$

$a_{n} = b_{n + 1} - b_{n} = (4 - n) \cdot 2^{n - 2} - (5 - n) \cdot 2^{n - 2} = \dots$

連立漸化式は行列を使うと統一的に扱える。ベクトル $1$ と行列 $A = 2$ を用いて $x_{n + 1} = A x_{n}$ と表せる。