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

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

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

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

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

$$a_n=a_{n-1}+n(n\ge 2),a_1=2$$

例：分かれた部分の個数

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

$$\begin{array}{rl}{a}_n& =2+\sum _{k=2}^{n}k\\ & =2+\left(\frac{n(n+1)}{2}-1\right)\\ & =\frac{n^2+n+2}{2}\end{array}$$

$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\ge 3),a_1=1,a_2=2$$

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

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

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

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

例：表が 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\ge 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}{\left(-\frac{1}{2}\right)}^n$$

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

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

赤玉 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{\left(\frac{4}{5}\right)}^{n-1}$$

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

立てたあとは型で解く

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

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

参考文献