漸化式の図形・確率への応用

漸化式は数列の問題だけに登場するわけではない。図形の分割や確率の推移など、一見すると数列とは無関係に見える問題でも、漸化式を立てることで鮮やかに解けるケースが数多く存在する。

図形への応用：平面の分割問題

$n$ 本の直線で平面をいくつの領域に分割できるかという古典的な問題を考えよう。ただし、どの 2 本も平行でなく、どの 3 本も 1 点で交わらないものとする。

$n$ 本の直線が作る領域の数を $a_{n}$ とおく。 $n$ 本目の直線を引くとき、この直線はすでにある $n - 1$ 本の直線それぞれと 1 回ずつ交わるため、 $n - 1$ 個の交点を持つ。これにより $n$ 本目の直線は $n$ 個の部分に分かれ、各部分が既存の領域を 2 つに分割する。よって新たに $n$ 個の領域が増える。

$a_{n} = a_{n - 1} + n (n \geq 2), a_{1} = 2$

これは階差型の漸化式であり、直接的に解ける。

$a_{n} = a_{1} + k = 2 \sum n k = 2 + \frac{n ( n + 1 )}{2} - 1 = \frac{n ^{2} + n + 2}{2}$

$n = 0$ （直線なし）のとき $a_{0} = 1$ とすると、 $a_{n} = \frac{n ^{2} + n + 2}{2}$ は $n = 0$ でも成り立つ。

直線の本数	領域の数
0	1
1	2
2	4
3	7
4	11
5	16

このように漸化式を立てて和を計算するだけで、図形の分割数が一般項として求まる。

図形への応用：階段の上り方

帰納的な発想が役立つ別の例として、「 $n$ 段の階段を 1 段または 2 段ずつ上る方法」を定式化してみよう。

$n$ 段目に到達する方法の数を $a_{n}$ とすると、直前が $n - 1$ 段目なら 1 段上がり、 $n - 2$ 段目なら 2 段上がるから、

$a_{n} = a_{n - 1} + a_{n - 2} (n \geq 3), a_{1} = 1, a_{2} = 2$

これはフィボナッチ数列と本質的に同じ構造を持っている。階段の段数を増やすたびに、過去 2 段分の情報だけから次の値が決まるという再帰構造が、漸化式の真骨頂といえる。

確率への応用：ランダムウォーク

数直線上の原点にいる粒子が、各ステップで確率 $\frac{1}{2}$ で右に 1、確率 $\frac{1}{2}$ で左に 1 動く問題を考える。 $n$ ステップ後に原点にいる確率 $p_{n}$ を求めたい。

$n$ が奇数のとき、 $n$ ステップ後に原点に戻ることは不可能なので $p_{n} = 0$ となる。 $n$ が偶数のとき、 $n = 2 m$ とおけば、 $m$ 回右に動き $m$ 回左に動く必要がある。

$p_{2 m} = (m 2 m) (\frac{1}{2})^{2 m}$

これ自体は漸化式ではないが、隣接する偶数ステップの確率の間には次の関係が成り立つ。

$p_{2 (m + 1)} = p_{2 m} \cdot \frac{2 m + 1}{2 ( m + 1 )}$

この漸化式から $m$ が大きくなるにつれて $p_{2 m}$ が単調に減少すること、つまり原点に戻る確率がだんだん小さくなることが直ちにわかる。

確率への応用：状態遷移の漸化式

確率と漸化式の組み合わせで最も頻出なのは、状態遷移を用いたパターンである。

問題設定

白玉 3 個と赤玉 2 個が入った袋から 1 個取り出し、色を確認して戻す。 $n$ 回目に白玉を取り出す確率を $p_{n}$ とするとき、 $p_{n}$ を求めよ。

考え方

この問題は毎回独立なので $p_{n} = \frac{3}{5}$ と即答できるが、「取り出した玉と異なる色の玉を戻す」などのルールを加えると状態が変化し、漸化式が必要になる。

より本質的な例として、次の問題を考えよう。コインを繰り返し投げ、表が 2 回連続で出たら終了するゲームで、ちょうど $n$ 回目に終了する確率 $q_{n}$ を求める。

$n$ 回目に初めて「表が 2 連続」になるには、直前の状況として 2 つのケースがある。

$n - 1$ 回目が裏であった場合から表表と続くケースと、 $n - 1$ 回目が「表 1 回の状態」であるケースを考えなければならない。ここで「現在の連続表の回数」を状態として定義するのがポイントとなる。

状態 0（直前が裏または開始時）にいる確率を $s_{n}$ 、状態 1（直前が表 1 回）にいる確率を $t_{n}$ とおくと、

$s_{n + 1} = \frac{1}{2} (s_{n} + t_{n}), t_{n + 1} = \frac{1}{2} s_{n}$

終了確率は $q_{n + 1} = \frac{1}{2} t_{n}$ で与えられる。 $t_{n}$ を消去すると、

$s_{n + 1} = \frac{1}{2} s_{n} + \frac{1}{4} s_{n - 1}$

という三項間漸化式に帰着する。初期値 $s_{1} = \frac{1}{2}$ , $s_{0} = 1$ から $s_{n}$ を求め、 $q_{n}$ を計算できる。

図形の問題

幾何的な増分を漸化式で捉える。 $n$ 本目の直線が何個の新しい領域を生むかという「差分」に着目するのがコツ

確率の問題

状態を定義し、各状態間の遷移確率を漸化式として記述する。状態の設計が解法の鍵を握る

漸化式を立てるコツ

図形でも確率でも、漸化式を立てる際のポイントは共通している。

まず「 $n$ の場合」と「 $n - 1$ の場合」の差を考えることである。図形なら $n$ 番目の要素を追加したときの変化量、確率なら 1 ステップ進めたときの状態遷移に注目する。

次に、必要な情報を過不足なく状態として定義することが重要になる。確率の問題で状態を多く取りすぎると連立漸化式が複雑になり、逆に少なすぎると情報が足りず立式できない。ちょうど必要十分な状態数を見極める力が、この分野の実力を左右する。

最後に、立てた漸化式がどの型に該当するかを判断し、適切な解法を適用する。等差・等比型、特性方程式型、三項間型など、基本的な漸化式の解法を一通り身につけておくことが前提となる。