入試では数列の知識が確率や図形と組み合わさった融合問題が頻出します。特に確率漸化式は東大・京大をはじめ難関大で繰り返し出題される重要テーマです。数列と図形の融合、数列と整数の融合も含めて攻略しましょう。
確率漸化式とは、$n$ 回の試行後の確率 $p_n$ を $p_{n-1}$（や $p_{n-2}$）を使った漸化式で表し、$p_n$ の一般項を求める問題です。
Step 1：状態を定義する（$n$ 回後にどの状態にいるかを場合分け）
Step 2：各状態の確率を $p_n$, $q_n$ などとおく
Step 3：$n$ 回目から $n+1$ 回目への推移を考えて漸化式を立てる
Step 4：漸化式を解いて $p_n$ を求める
※ 状態が2つなら $q_n = 1 - p_n$ で変数を1つに減らせます。
問題：コインを繰り返し投げ、表が出たら右に1歩、裏が出たら左に1歩進む。原点を出発して $n$ 回後に原点にいる確率 $p_n$ を求めよ。ただしコインの表が出る確率は $\frac{1}{2}$ とする。
解：$n$ が奇数のとき、$n$ 回後に原点にいることは不可能なので $p_n = 0$。
$n$ が偶数のとき、$n = 2m$ とおくと $m$ 回表、$m$ 回裏が出ればよいので：
$$p_{2m} = \binom{2m}{m}\left(\frac{1}{2}\right)^{2m} = \frac{(2m)!}{(m!)^2 \cdot 4^m}$$
（この問題は漸化式なしでも解けますが、状態遷移の考え方を学ぶ導入です。）
確率漸化式では「何を状態として定義するか」が解法の成否を左右します。
状態は「今どこにいるか」「今どの色か」「何個残っているか」など、次の試行の結果を左右する情報を過不足なく含むように設定します。
典型的な確率漸化式は $p_{n+1} = ap_n + b$ の形（1次漸化式）になり、特性方程式で解けます。
問題：AとBがじゃんけんを繰り返す。$n$ 回後にAが勝ち越している確率を $p_n$ とする。ただし各回でAが勝つ確率、負ける確率、あいこの確率はいずれも $\frac{1}{3}$ とし、$p_0 = 0$ とする。$p_n$ を $n$ で表せ。
解：Aの勝ち越し数で状態を分類するのは複雑なので、より単純な問題に変形します。
$n$ 回目にAが勝っている（累計勝数 $>$ 累計負数）状態を $p_n$、引き分け（$=$）を $q_n$、負けている（$<$）を $r_n$ とすると、対称性より $p_n = r_n$。
$p_n + q_n + r_n = 1$ と $p_n = r_n$ より $q_n = 1 - 2p_n$。
$p_{n+1} = p_n \cdot \frac{1}{3}(\text{勝}) + p_n \cdot \frac{1}{3}(\text{あいこ}) + p_n \cdot \frac{1}{3}(\text{負}) + q_n \cdot \frac{1}{3}(\text{Aが勝つ})$
勝ち越し状態で勝っても負けても勝ち越しのままとは限りません。正確には状態遷移を考え直す必要がありますが、ここでは対称性を利用した典型問題の解法に焦点を当てます。
問題：部屋A, B, Cがあり、AからはBまたはCに等確率（$\frac{1}{2}$ ずつ）で移動、BからはAまたはCに等確率で移動、CからはAまたはBに等確率で移動する。最初に部屋Aにいるとき、$n$ 回移動後に部屋Aにいる確率 $p_n$ を求めよ。
解：対称性より、$n$ 回後にBにいる確率とCにいる確率は等しい。これを $q_n$ とする。
$p_n + 2q_n = 1$ より $q_n = \frac{1-p_n}{2}$。
$p_{n+1} = 0 \cdot p_n + \frac{1}{2} q_n + \frac{1}{2} q_n = q_n = \frac{1-p_n}{2}$
（Aにいたらそのままにはなれない。B, Cのいずれかから $\frac{1}{2}$ で戻る。）
$$p_{n+1} = -\frac{1}{2}p_n + \frac{1}{2}$$
特性方程式：$\alpha = -\frac{1}{2}\alpha + \frac{1}{2}$ より $\alpha = \frac{1}{3}$。
$p_{n+1} - \frac{1}{3} = -\frac{1}{2}\left(p_n - \frac{1}{3}\right)$
$p_n - \frac{1}{3} = \left(-\frac{1}{2}\right)^{n-1} \cdot \left(p_1 - \frac{1}{3}\right)$。$p_0 = 1$（最初はAにいる）なので $p_1 = 0$。
$p_n - \frac{1}{3} = \left(-\frac{1}{2}\right)^{n-1}\left(-\frac{1}{3}\right)$。$p_0 = 1$ を使い直すと：
$p_n - \frac{1}{3} = \left(-\frac{1}{2}\right)^n\left(1 - \frac{1}{3}\right) = \frac{2}{3}\left(-\frac{1}{2}\right)^n$
$$p_n = \frac{1}{3} + \frac{2}{3}\left(-\frac{1}{2}\right)^n = \frac{1 + 2 \cdot (-1)^n \cdot 2^{-n}}{3} = \frac{1+(-1)^n \cdot 2^{1-n}}{3}$$
✗ 「最初に部屋Aにいる」を $p_1 = 1$ と設定（$0$ 回移動後を $n = 1$ とする混乱）
✓ 移動前（$0$ 回移動後）を $p_0 = 1$ と定め、$p_1 = 0$（1回移動すると必ずAを離れる）
$n$ の定義（移動回数か試行回数か）と初期条件を正確に対応させましょう。
図形の操作を繰り返すことで、面積や長さが数列を成す問題です。
問題：1辺の長さが $1$ の正三角形の各辺の中点を結んで内部に正三角形を作る操作を繰り返す。$n$ 回目の操作後に新たに現れる正三角形（上向き）の1辺の長さ $a_n$ と個数 $b_n$ を求め、新たに現れる三角形の面積の総和 $S_n$ を求めよ。
解：1回目：$a_1 = \frac{1}{2}$、$b_1 = 1$個（中央の逆向き三角形は除く）。
実は各辺の中点を結ぶと $4$ つの正三角形に分割され、うち $3$ つが上向き（元と同じ向き）、$1$ つが逆向きです。
$n$ 回の操作後：辺の長さ $a_n = \frac{1}{2^n}$、面積は $\frac{\sqrt{3}}{4} \cdot a_n^2 = \frac{\sqrt{3}}{4^{n+1}}$。
各操作で三角形の数は $3$ 倍になるので $b_n = 3^{n-1}$（$n \geq 1$）。
$S_n = b_n \cdot \frac{\sqrt{3}}{4} \cdot a_n^2 = 3^{n-1} \cdot \frac{\sqrt{3}}{4} \cdot \frac{1}{4^n} = \frac{\sqrt{3}}{4} \cdot \frac{3^{n-1}}{4^n} = \frac{\sqrt{3}}{12} \left(\frac{3}{4}\right)^n$
パターン1：相似比 $r$ の繰り返し → 面積は公比 $r^2$ の等比数列
パターン2：個数が倍々に増える → 等比数列
パターン3：面積の総和 → 等比級数の和（無限級数の場合も）
※ 無限回操作の極限は等比級数の和の公式 $\frac{a}{1-r}$ で求められます。
上の操作を無限に繰り返すと「シェルピンスキーの三角形」と呼ばれるフラクタル図形になります。
残る部分の面積は $\left(\frac{3}{4}\right)^n \to 0$ となり、面積は $0$ ですが点は無限に残るという不思議な図形です。
数列の各項が整数であることを利用して、倍数性や余りの周期性を調べる問題です。
問題：フィボナッチ数列 $F_1 = 1, F_2 = 1, F_{n+2} = F_{n+1} + F_n$ について、$F_n$ を $3$ で割った余りの周期を求めよ。
解：$F_n \mod 3$ を順に計算：
$1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, \ldots$
余りの列は周期 $8$ で繰り返す：$(1, 1, 2, 0, 2, 2, 1, 0)$。
よって $F_n \equiv 0 \pmod{3} \iff n \equiv 0 \pmod{4}$。
すなわち $4$ の倍数番目のフィボナッチ数が $3$ の倍数になる。
フィボナッチ数列を $m$ で割った余りの列は必ず周期的になります。この周期をピサノ周期と呼びます。
連続する2項 $(F_n \bmod m, F_{n+1} \bmod m)$ の組合せは $m^2$ 通りしかないため、有限回で同じ組が再現し、以後繰り返します。
問題：$a_1 = 1$, $a_{n+1} = 3a_n + 2$ のとき、$a_n$ を $5$ で割った余りを求めよ。
解：$a_n \mod 5$ を順に計算：$1, 0, 2, 3, 1, 0, 2, 3, \ldots$
周期 $4$：$(1, 0, 2, 3)$。
一般項 $a_n = \frac{3^n - 1}{2} \cdot 2 + 3^n \cdot \ldots$ を直接求めると $a_n = 2 \cdot 3^{n-1} - 1$。
$3^n \mod 5$ の周期は $4$：$(3, 4, 2, 1, 3, \ldots)$。
$a_n = 2 \cdot 3^{n-1} - 1 \mod 5$ の周期も $4$ で確認できる。
✗ 一般項を求めてから余りを計算しようとして分数が出現し混乱する
✓ 余りだけが必要なら、漸化式に直接 $\bmod$ を適用して余りの列を求める
$a_{n+1} \equiv 3a_n + 2 \pmod{5}$ として計算する方が確実です。
融合問題を解く際の一般的な戦略をまとめます。
1. 状況の把握：何が繰り返されるのか、何が $n$ に依存するのかを明確にする
2. 数列の定義：$n$ に依存する量を $a_n$, $p_n$ などと定義する
3. 漸化式の導出：$n$ 回目から $n+1$ 回目への関係（推移）を立式する
4. 漸化式を解く：等差・等比・特性方程式などの既知の方法で一般項を求める
5. 検算：$n = 1, 2$ 程度で具体値を確認する
融合問題の難しさは「漸化式を解くこと」よりも「漸化式を正しく立てること」にあります。
状態の設定、推移の場合分け、初期条件の確認を丁寧に行いましょう。漸化式さえ正しく立てられれば、あとは数列の章で学んだ技法で解けます。
確率漸化式の一般項に含まれる $\left(-\frac{1}{2}\right)^n$ や $\left(\frac{1}{3}\right)^n$ は $n \to \infty$ で $0$ に収束します。
したがって極限確率 $\lim_{n \to \infty} p_n$ は漸化式の特性方程式の解（定常確率）に一致します。3部屋の問題なら $\frac{1}{3}$ です。
Q1. 確率漸化式で最初に行うべきことは何か。
Q2. 3部屋の移動問題で $p_0 = 1$, $p_1 = 0$ となる理由を述べよ。
Q3. 相似比 $\frac{1}{2}$ の操作を繰り返すとき、面積の公比はいくつか。
Q4. フィボナッチ数列を $3$ で割った余りの周期を答えよ。
Q5. 確率漸化式の極限値は何を表すか。
赤白2つの箱がある。最初に赤の箱にボールが入っている。毎回 $\frac{2}{3}$ の確率で箱を入れ替え、$\frac{1}{3}$ の確率でそのままにする。$n$ 回後にボールが赤の箱にある確率 $p_n$ を求めよ。
$p_0 = 1$。漸化式：$p_{n+1} = \frac{1}{3}p_n + \frac{2}{3}(1-p_n) = -\frac{1}{3}p_n + \frac{2}{3}$
特性方程式：$\alpha = -\frac{1}{3}\alpha + \frac{2}{3}$ より $\alpha = \frac{1}{2}$。
$p_{n+1} - \frac{1}{2} = -\frac{1}{3}\left(p_n - \frac{1}{2}\right)$
$p_n - \frac{1}{2} = \left(-\frac{1}{3}\right)^n \cdot \left(1 - \frac{1}{2}\right) = \frac{1}{2}\left(-\frac{1}{3}\right)^n$
$$p_n = \frac{1}{2} + \frac{1}{2}\left(-\frac{1}{3}\right)^n = \frac{1+(-1)^n \cdot 3^{-n}}{2}$$
1辺の長さ $1$ の正方形の各辺の中点を結んで内部に正方形を作る操作を $n$ 回繰り返す。$n$ 回目の操作で作った正方形の面積 $S_n$ を求めよ。また $\sum_{k=1}^{\infty} S_k$ を求めよ。
各辺の中点を結んだ正方形の1辺は、元の正方形の1辺の $\frac{1}{\sqrt{2}}$ 倍。
$n$ 回操作後の正方形の1辺：$\left(\frac{1}{\sqrt{2}}\right)^n = \frac{1}{(\sqrt{2})^n}$
面積：$S_n = \left(\frac{1}{\sqrt{2}}\right)^{2n} = \frac{1}{2^n} = \left(\frac{1}{2}\right)^n$
$\sum_{k=1}^{\infty} S_k = \sum_{k=1}^{\infty} \left(\frac{1}{2}\right)^k = \frac{\frac{1}{2}}{1 - \frac{1}{2}} = 1$
数直線上の原点に点Pがいる。毎回サイコロを振り、$1, 2$ の目が出たら $+1$、$3, 4, 5, 6$ の目が出たら $-1$ 移動する。$n$ 回後にPが原点にいる確率 $p_n$ について、$p_1$, $p_2$ を求めよ。
$+1$ の確率は $\frac{2}{6} = \frac{1}{3}$、$-1$ の確率は $\frac{4}{6} = \frac{2}{3}$。
$p_1 = 0$（1回移動すると必ず $+1$ か $-1$ のどちらかへ移動するため原点にはいない）。
$p_2$：2回で原点に戻るには $+1, -1$ または $-1, +1$ の順。
$p_2 = \frac{1}{3} \cdot \frac{2}{3} + \frac{2}{3} \cdot \frac{1}{3} = \frac{2}{9} + \frac{2}{9} = \frac{4}{9}$
頂点A, B, Cをもつ正三角形上を動く点Pがある。毎回 $\frac{1}{2}$ の確率で隣接する2頂点のいずれかに移動する。Pが頂点Aから出発して $n$ 回後に頂点Aにいる確率 $p_n$ を求めよ。
対称性より、$n$ 回後にBにいる確率とCにいる確率は等しい。これを $q_n$ とする。
$p_n + 2q_n = 1$ より $q_n = \frac{1-p_n}{2}$。
$p_{n+1} = \frac{1}{2} q_n + \frac{1}{2} q_n = q_n = \frac{1-p_n}{2}$
$p_{n+1} = -\frac{1}{2}p_n + \frac{1}{2}$
特性方程式：$\alpha = -\frac{1}{2}\alpha + \frac{1}{2}$ より $\alpha = \frac{1}{3}$。
$p_{n+1} - \frac{1}{3} = -\frac{1}{2}\left(p_n - \frac{1}{3}\right)$
$p_0 = 1$ より $p_n - \frac{1}{3} = \left(-\frac{1}{2}\right)^n \cdot \frac{2}{3}$
$$p_n = \frac{1}{3} + \frac{2}{3}\left(-\frac{1}{2}\right)^n = \frac{1+2(-1)^n \cdot 2^{-n}}{3}$$
正三角形上の対称性から3つの状態を2つ（AとA以外）に集約できることがポイントです。$n \to \infty$ で $p_n \to \frac{1}{3}$ となり、十分長い時間後にはどの頂点にいる確率も等しく $\frac{1}{3}$ になるという直感と一致します。