漸化式の立て方（直線が分ける領域、階段の上り方、確率の問題）

$n$ 本の直線で平面がいくつの部分に分かれるかを数えます。どの 2 本も平行でなく、どの 3 本も 1 点では交わらないものとする。

いきなり一般項を作ろうとせず、1 本足したときに何個増えるかだけを見ます。

$n$ 本目の直線は、先にある $n - 1$ 本すべてと 1 回ずつ交わります。交点が $n - 1$ 個できるため、この直線自身が $n$ 個の部分に切られる。

切られた $n$ 個の部分が、それぞれ通り抜けた領域を 2 つに分ける。よって領域は $n$ 個増える^[1]。

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

例：分かれた部分の個数

階差の形なので、増えぶんを足し上げます^[2]。

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

直線の本数	分かれた部分の個数
0	1
1	2
2	4
3	7
4	11
5	16

$n = 0$ を入れると $1$ になり、直線が 1 本もないときの平面 1 個と合います。 $n = 100$ なら $\frac{10000 + 100 + 2}{2} = 5051$ 個で、数え上げでは追えない値も式なら計算できる。

階段の上り方は最後の一歩で分かれる

$n$ 段の階段を、1 段ずつか 2 段ずつで上ります。上り方が何通りあるかを $a_{n}$ と置く。

最後の一歩に注目します。1 段で上がったなら直前は $n - 1$ 段目、2 段で上がったなら直前は $n - 2$ 段目にいたことになる。

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

$1, 2, 3, 5, 8, 13, \dots$ と続き、フィボナッチ数列と同じ並びになりました。最後の一歩で場合分けする、という切り口が漸化式をそのまま作る。

確率は状態を決めてから立てる

確率の問題では、何を状態とするかを決めるところで手が止まります。状態が決まれば、そこからの移り方が漸化式そのもの。

n 番目を足したときの変化だけを見る

確率なら、次を決めるのに必要な情報を状態にする

できた漸化式の型を見分けて解く

状態は多すぎると連立が重くなり、少なすぎると立式できません。次の一手を決めるのに何が必要か、そこだけを基準に選びます。

例：表が 2 回続かない確率

コインを $n$ 回投げて、表が 2 回続いたことが一度もない確率を $p_{n}$ と置きます。

最後の 1 回で場合を分ける。裏だったなら、その前の $n - 1$ 回で条件を満たしていればよいので $\frac{1}{2} p_{n - 1}$ 。

表だったなら、その 1 つ前は裏でなければなりません。裏表と続く確率が $\frac{1}{4}$ で、そこまでの $n - 2$ 回が条件を満たせばよい。

$p_{n} = \frac{1}{2} p_{n - 1} + \frac{1}{4} p_{n - 2} (n \geq 2), p_{0} = 1, p_{1} = 1$

$p_{2} = \frac{1}{2} + \frac{1}{4} = \frac{3}{4}$ 。2 回投げて表表になる確率が $\frac{1}{4}$ なので、残りが $\frac{3}{4}$ で合います。

$p_{3} = \frac{1}{2} \cdot \frac{3}{4} + \frac{1}{4} = \frac{5}{8}$ 。3 回の並び 8 通りのうち、表表を含まないものを数えると 5 通りで一致しました。

例：正三角形の頂点をまわる点

正三角形の頂点 $A$ 、 $B$ 、 $C$ を点 $P$ が動きます。1 回の移動で、いまいる頂点以外の 2 つへ等しい確率で移る。

$P$ が最初 $A$ にいるとして、 $n$ 回移動したあとに $A$ にいる確率を $p_{n}$ と置く。

$A$ にいるためには、直前が $B$ か $C$ で、そこから $A$ を選ぶ必要があります。直前に $A$ にいなかった確率が $1 - p_{n}$ 、そこから $A$ を選ぶ確率が $\frac{1}{2}$ 。

$p_{n + 1} = \frac{1}{2} (1 - p_{n})$

特性方程式 $x = \frac{1}{2} (1 - x)$ から $x = \frac{1}{3}$ 。 $p_{0} = 1$ で始めます。

$p_{n} = \frac{1}{3} + \frac{2}{3} (- \frac{1}{2})^{n}$

$p_{1} = 0$ 、 $p_{2} = \frac{1}{2}$ 、 $p_{3} = \frac{1}{4}$ と続き、回数が増えるほど $\frac{1}{3}$ に近づく。3 つの頂点は対等だから、長い目で見た確率が等しくなるのは自然です。

$n$ 本の直線が平面を分ける個数で、 $5$ 本のときはいくつですか。

$11$
$16$
$21$
$32$

__RESULT__

$a_{5} = a_{4} + 5 = 11 + 5 = 16$ です。式 $\frac{n ^{2} + n + 2}{2}$ に $n = 5$ を入れても $\frac{25 + 5 + 2}{2} = 16$ になります。

例：袋の中身が変わる操作

赤玉 2 個と白玉 3 個の袋から 1 個とり出し、白玉なら赤玉に替えて戻します。赤玉ならそのまま戻す。

袋のなかの赤玉が何個かで状態を分けると数が多くなるため、赤玉の個数の期待値 $e_{n}$ を追う。

赤玉が増えるのは白玉を引いたときで、赤が $k$ 個なら白は $5 - k$ 個。引く確率は $\frac{5 - k}{5}$ です。

$e_{n + 1} = e_{n} + \frac{5 - e _{n}}{5} = \frac{4}{5} e_{n} + 1$

$e_{1} = 2$ から始め、特性方程式 $x = \frac{4}{5} x + 1$ を解くと $x = 5$ 。

$e_{n} = 5 - 3 (\frac{4}{5})^{n - 1}$

$e_{2} = 5 - \frac{12}{5} = \frac{13}{5}$ で、漸化式に $e_{1} = 2$ を入れた $\frac{8}{5} + 1$ と合います。くり返すほど $5$ に近づき、最後は全部が赤玉になるという見当と重なる。

立てたあとは型で解く

図形では増えぶんに注目し、確率では状態を選ぶ。そこから先は、できた漸化式の型で決まります。

階差型 $a_{n + 1} = a_{n} + f (n)$	増えぶんを足し上げる
$a_{n + 1} = p a_{n} + q$ 型	特性方程式で定数を消す
三項間 $a_{n + 2} = p a_{n + 1} + q a_{n}$	特性方程式の 2 解から作る

確率の問題で漸化式を立てるとき、状態はどう選びますか。

初期値が大きくなるように選ぶ
次を決めるのに必要な情報がそろうように選ぶ
できるだけ多く用意する
期待値だけを状態にする

__RESULT__

状態が足りないと立式できず、多すぎると連立が重くなります。次の一手を決めるのに何が必要かだけを見て選びます。

$n$ 番目を足したときに何がどれだけ増えるか。直線でも階段でも確率でも、見るところは変わりません。

参考文献

Plane Division by Lines. Wolfram MathWorld.

Discrete Mathematics: An Open Introduction, 2.4 Solving Recurrence Relations. Oscar Levin, 3rd edition.

$n$ 本目の直線は先にある $n-1$ 本すべてと交わり、自分自身が $n$ 個に切られるので、平面の分かれ方は $n$ 個だけ増えます。$a_n = a_{n-1} + n$ を足し上げれば $\dfrac{n^2+n+2}{2}$ で、$100$ 本なら $5051$ 個。階段の上り方は最後の一歩で場合分けするとフィボナッチ数列と同じ並びになり、確率では状態を決めた時点で移り方がそのまま漸化式になります。表が 2 回続かない確率、正三角形の頂点をまわる点、袋の中身が変わる操作の期待値まで。