連立漸化式では2つの数列 $\{a_n\}$, $\{b_n\}$ が互いに影響し合いながら変化します。$a_{n+1} = pa_n + qb_n$, $b_{n+1} = ra_n + sb_n$ の形の漸化式を、和と差の新しい数列を作ることで独立した漸化式に分離する手法を学びます。
2つの数列 $\{a_n\}$, $\{b_n\}$ が次のような関係で結ばれている場合を連立漸化式と呼びます。
$$\begin{cases} a_{n+1} = pa_n + qb_n \\ b_{n+1} = ra_n + sb_n \end{cases}$$
初期条件として $a_1, b_1$ が与えられる。
$a_{n+1}$ が $b_n$ に依存し、$b_{n+1}$ が $a_n$ に依存するため、どちらか一方だけでは解けません。2つの式を連立して処理する必要があります。
2つの数列が「絡み合って」いる状態を、適切な線形結合（和・差・定数倍の組み合わせ）で「解きほぐす」のが基本戦略です。
$c_n = a_n + kb_n$ の形の新しい数列を作り、$c_n$ だけの漸化式（等比型など）に帰着させます。
最もよく出題されるのは、和と差を取ることで分離できるタイプです。
例：$a_{n+1} = 2a_n + b_n$, $b_{n+1} = a_n + 2b_n$, $a_1 = 3$, $b_1 = 1$ の一般項を求めよ。
和：$a_{n+1} + b_{n+1} = 3a_n + 3b_n = 3(a_n + b_n)$
$s_n = a_n + b_n$ と置くと $s_{n+1} = 3s_n$, $s_1 = 4$ で $s_n = 4 \cdot 3^{n-1}$。
差：$a_{n+1} - b_{n+1} = a_n - b_n$
$d_n = a_n - b_n$ と置くと $d_{n+1} = d_n$, $d_1 = 2$ で $d_n = 2$。
逆算：$a_n = \frac{s_n + d_n}{2} = \frac{4 \cdot 3^{n-1} + 2}{2} = 2 \cdot 3^{n-1} + 1$
$b_n = \frac{s_n - d_n}{2} = \frac{4 \cdot 3^{n-1} - 2}{2} = 2 \cdot 3^{n-1} - 1$
✗ $a_{n+1} = 3a_n + b_n$, $b_{n+1} = a_n + 4b_n$ に対して $a_n + b_n$ を計算 → $a_{n+1} + b_{n+1} = 4a_n + 5b_n$ となり $a_n + b_n$ だけの式にならない
✓ 係数が対称的（$p = s$）でない場合は、単純な和と差では分離できないことが多い。次節の一般的な方法を使う
$a_{n+1} = pa_n + qb_n$, $b_{n+1} = qa_n + pb_n$（$p$ と $q$ の位置が対称的な場合）は、和と差で分離できます。
和：$s_{n+1} = (p+q)s_n$（等比数列）、差：$d_{n+1} = (p-q)d_n$（等比数列）
係数が対称的でない場合は、$c_n = a_n + kb_n$ の形で $k$ を適切に定めます。
$c_n = a_n + kb_n$ が等比数列になるための条件：
$c_{n+1} = a_{n+1} + kb_{n+1} = (p + kr)a_n + (q + ks)b_n = \lambda(a_n + kb_n) = \lambda c_n$
これが成り立つためには $\frac{p + kr}{1} = \frac{q + ks}{k} = \lambda$ すなわち
$$k(p + kr) = q + ks \quad \Longleftrightarrow \quad rk^2 + (p - s)k - q = 0$$
例：$a_{n+1} = 3a_n + b_n$, $b_{n+1} = 2a_n + 4b_n$, $a_1 = 1$, $b_1 = 0$ の一般項を求めよ。
$c_n = a_n + kb_n$ とし、$rk^2 + (p-s)k - q = 0$（$r=2, p=3, s=4, q=1$）を解く：
$2k^2 - k - 1 = 0$、$(2k + 1)(k - 1) = 0$ で $k = 1$ または $k = -\frac{1}{2}$。
$k = 1$ のとき：$c_n = a_n + b_n$, $\lambda = p + kr = 3 + 2 = 5$
$c_{n+1} = 5c_n$, $c_1 = 1$ で $c_n = 5^{n-1}$。
$k = -\frac{1}{2}$ のとき：$c_n' = a_n - \frac{1}{2}b_n$, $\lambda' = 3 + 2(-\frac{1}{2}) = 2$
$c_{n+1}' = 2c_n'$, $c_1' = 1$ で $c_n' = 2^{n-1}$。
逆算：$c_n - c_n' = \frac{3}{2}b_n$ より $b_n = \frac{2}{3}(5^{n-1} - 2^{n-1})$
$a_n = c_n' + \frac{1}{2}b_n = 2^{n-1} + \frac{1}{3}(5^{n-1} - 2^{n-1}) = \frac{2}{3} \cdot 2^{n-1} + \frac{1}{3} \cdot 5^{n-1}$
$= \frac{2^n + 5^{n-1}}{3}$
検算：$a_1 = \frac{2 + 1}{3} = 1$ ✓, $b_1 = \frac{2}{3}(1 - 1) = 0$ ✓
$rk^2 + (p-s)k - q = 0$ の2つの解 $k_1, k_2$ は、連立漸化式を「独立な2つの等比数列」に分解するための係数です。
この方程式は、後述する行列の固有値問題と密接に関連しています。
確率の問題で現れる漸化式は、しばしば連立型になります。
例：状態 A, B の2つがあり、A にいる確率 $a_n$、B にいる確率 $b_n$ とする。各ステップで A から B へ確率 $\frac{1}{3}$ で移動、B から A へ確率 $\frac{1}{2}$ で移動するとき、$a_n$ を求めよ。初期状態は A（$a_1 = 1$）。
$$a_{n+1} = \frac{2}{3}a_n + \frac{1}{2}b_n, \quad b_{n+1} = \frac{1}{3}a_n + \frac{1}{2}b_n$$
$a_n + b_n = 1$（確率の和は $1$）を利用して $b_n = 1 - a_n$ を代入：
$a_{n+1} = \frac{2}{3}a_n + \frac{1}{2}(1 - a_n) = \frac{1}{6}a_n + \frac{1}{2}$
$a_{n+1} - \frac{3}{5} = \frac{1}{6}\left(a_n - \frac{3}{5}\right)$
$a_n - \frac{3}{5} = \frac{2}{5}\left(\frac{1}{6}\right)^{n-1}$ より $a_n = \frac{3}{5} + \frac{2}{5}\left(\frac{1}{6}\right)^{n-1}$
確率漸化式では $a_n + b_n = 1$（すべての状態の確率の和が $1$）という条件が常に成り立ちます。この条件を使えば連立漸化式を1つの漸化式に帰着できるため、一般の連立漸化式より簡単に解けます。
状態が3つ以上の場合も、対称性を利用して実質的に2つの数列の問題に帰着させるのが定石です。
✗ $a_n + b_n = 1$ の条件を忘れ、連立漸化式をそのまま一般的な方法で解く（計算が無駄に複雑になる）
✓ まず $b_n = 1 - a_n$ を代入して $a_n$ だけの漸化式にするのが最善手
連立漸化式は行列を用いて統一的に表現できます。
$$\begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix} p & q \\ r & s \end{pmatrix} \begin{pmatrix} a_n \\ b_n \end{pmatrix}$$
$M = \begin{pmatrix} p & q \\ r & s \end{pmatrix}$ と置くと $\mathbf{x}_{n} = M^{n-1}\mathbf{x}_1$。
※ $M$ の固有値が前節の $\lambda$ に対応し、固有ベクトルが分離の方向 $(1, k)$ に対応します。
行列 $M = \begin{pmatrix} p & q \\ r & s \end{pmatrix}$ の固有方程式は：
$\det(M - \lambda I) = (p - \lambda)(s - \lambda) - qr = \lambda^2 - (p+s)\lambda + (ps - qr) = 0$
セクション3で求めた $k$ に対する $\lambda = p + kr$ は、まさにこの固有方程式の解です。
連立漸化式を解くことは、行列の固有値分解（対角化）と同じ操作です。
高校数学では行列を直接扱いませんが、「和と差を取る」「適切な線形結合を作る」という操作の背景には固有値分解の考え方があります。
大学の線形代数で学ぶ対角化は、連立漸化式・連立微分方程式を解く統一的な方法論を提供します。
Q1. $a_{n+1} = 3a_n + 2b_n$, $b_{n+1} = 2a_n + 3b_n$ のとき $a_n + b_n$ の漸化式を求めよ。
Q2. Q1で $a_n - b_n$ の漸化式を求めよ。
Q3. 連立漸化式で $c_n = a_n + kb_n$ が等比数列になる $k$ を求める方程式は何か。
Q4. 確率漸化式で $a_n + b_n = 1$ を利用するメリットは何か。
Q5. $a_{n+1} = 5a_n - 2b_n$, $b_{n+1} = 2a_n + b_n$, $a_1 = 1, b_1 = 0$ のとき $a_n + b_n$ を求めよ。
$a_{n+1} = 4a_n + 3b_n$, $b_{n+1} = 3a_n + 4b_n$, $a_1 = 2$, $b_1 = 1$ のとき $a_n, b_n$ を求めよ。
$s_n = a_n + b_n$：$s_{n+1} = 7s_n$, $s_1 = 3$ より $s_n = 3 \cdot 7^{n-1}$。
$d_n = a_n - b_n$：$d_{n+1} = d_n$, $d_1 = 1$ より $d_n = 1$。
$a_n = \frac{3 \cdot 7^{n-1} + 1}{2}$, $b_n = \frac{3 \cdot 7^{n-1} - 1}{2}$。
$a_{n+1} = 4a_n + b_n$, $b_{n+1} = 2a_n + 3b_n$, $a_1 = 1$, $b_1 = 2$ のとき $a_n, b_n$ を求めよ。
$c_n = a_n + kb_n$ が等比数列になる $k$：$2k^2 + (4-3)k - 1 = 0$、$2k^2 + k - 1 = 0$。
$(2k - 1)(k + 1) = 0$ で $k = \frac{1}{2}$ または $k = -1$。
$k = \frac{1}{2}$：$c_n = a_n + \frac{1}{2}b_n$, $\lambda = 4 + 2 \cdot \frac{1}{2} = 5$。$c_1 = 2$, $c_n = 2 \cdot 5^{n-1}$。
$k = -1$：$c_n' = a_n - b_n$, $\lambda' = 4 + 2(-1) = 2$。$c_1' = -1$, $c_n' = -2^{n-1}$。
$c_n - c_n' = \frac{3}{2}b_n$ より $b_n = \frac{2}{3}(2 \cdot 5^{n-1} + 2^{n-1})$。
$a_n = c_n' + b_n = -2^{n-1} + \frac{2}{3}(2 \cdot 5^{n-1} + 2^{n-1}) = \frac{4}{3} \cdot 5^{n-1} - \frac{1}{3} \cdot 2^{n-1}$。
$k$ の2次方程式の2つの解が、2つの「独立な方向」を与えます。それぞれの方向で等比数列が得られ、元の数列はそれらの線形結合で表されます。
点 P が頂点 A, B, C からなる正三角形の頂点上を移動する。各ステップで現在の頂点にとどまる確率が $\frac{1}{3}$、他の各頂点に移動する確率がそれぞれ $\frac{1}{3}$ である。P が最初に A にいるとき、$n$ ステップ後に A にいる確率 $a_n$ を求めよ。
対称性から B にいる確率 $= $ C にいる確率 $= b_n$ とする。$a_n + 2b_n = 1$。
$a_{n+1} = \frac{1}{3}a_n + \frac{1}{3}b_n + \frac{1}{3}b_n = \frac{1}{3}a_n + \frac{2}{3}b_n = \frac{1}{3}a_n + \frac{2}{3} \cdot \frac{1-a_n}{2} = \frac{1}{3}a_n + \frac{1}{3}(1 - a_n) = \frac{1}{3}$
したがって $a_n = \frac{1}{3}$（$n \geq 2$）。$a_1 = 1$。
実はすべての頂点が等確率 $\frac{1}{3}$ で遷移するため、1ステップ後から定常状態 $\frac{1}{3}$ になります。
この問題は遷移確率がすべて等しい特殊な場合です。より一般的な確率漸化式（遷移確率が異なる場合）では $a_{n+1} = \alpha a_n + \beta$ の形になり、等比型に帰着させて解きます。
3つの部屋 A, B, C がある。A と B, B と C はそれぞれ行き来できるが、A と C の間は直接行けない。各ステップで隣の部屋に等確率で移動する（A からは B のみ、B からは A, C に各 $\frac{1}{2}$、C からは B のみ）。最初に A にいるとき、$n$ ステップ後に A にいる確率 $a_n$ を求めよ。
$a_n$：A にいる確率、$b_n$：B にいる確率、$c_n$：C にいる確率。
$a_{n+1} = \frac{1}{2}b_n$, $b_{n+1} = a_n + c_n$, $c_{n+1} = \frac{1}{2}b_n$
$a_{n+1} = c_{n+1}$ であり、$a_1 = 1, c_1 = 0$ なので $a_2 = c_2$。$n \geq 2$ で $a_n = c_n$。
$a_n + b_n + c_n = 1$ と $a_n = c_n$（$n \geq 2$）から $b_n = 1 - 2a_n$。
$a_{n+1} = \frac{1}{2}b_n = \frac{1}{2}(1 - 2a_n) = \frac{1}{2} - a_n$（$n \geq 2$）
$a_{n+1} - \frac{1}{4} = -(a_n - \frac{1}{4})$ より $a_n - \frac{1}{4} = (-1)^{n-2}(a_2 - \frac{1}{4})$（$n \geq 2$）。
$a_2 = \frac{1}{2}b_1 = 0$（$b_1 = 0$）なので $a_n = \frac{1}{4} + (-1)^{n-2} \cdot (-\frac{1}{4}) = \frac{1}{4}(1 + (-1)^{n-1})$（$n \geq 2$）。
$n$ が奇数のとき $a_n = \frac{1}{2}$, $n$ が偶数のとき $a_n = 0$（$n \geq 2$）。
$a_1 = 1$, $a_n = \frac{1 + (-1)^{n+1}}{4}$（$n \geq 2$）。
A から出発すると B にしか行けず、B から A と C に等確率で分かれます。奇数ステップでは A または C にいて、偶数ステップでは必ず B にいるという振動的な挙動を示します。対称性の活用が計算を簡略化する鍵です。