漸化式と数学的帰納法 ★★★★ 難関の問題 全8問

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+2}=5a_{n+1}-6a_n$ のような $3$ 項間漸化式は、$2$ つの等比数列の重ね合わせで書ける。

その公比を求めるのが特性方程式 $x^2=5x-6$。$2$ 次方程式の係数が漸化式の係数 $5,-6$ にそのまま対応する。解くと $x=2,3$ の異なる $2$ 解。だから一般項は $a_n=A\cdot 2^{n-1}+B\cdot 3^{n-1}$ の形になる。

あとは $a_1,a_2$ の値を代入して、$A,B$ を連立で決めるだけ。

① 特性方程式。 $x^2=5x-6$、すなわち $x^2-5x+6=(x-2)(x-3)=0$ より $x=2,3$。よって

$$a_n=A\cdot 2^{n-1}+B\cdot 3^{n-1}$$

② 係数を決める。 $a_1=1$、$a_2=4$ より

$$A+B=1,2A+3B=4$$

第 $2$ 式 $-$ 第 $1$ 式 $\times 2$:$B=2$。よって $A=-1$。

③ 一般項。

$$a_n=-2^{n-1}+2\cdot 3^{n-1}$$

(検算:$a_1=-1+2=1$、$a_2=-2+6=4$。)

まとめ:$3$ 項間漸化式は「特性方程式 → 異なる $2$ 解なら $A{\alpha }^{n-1}+B{\beta }^{n-1}$」。$2$ 解 $2,3$ を公比とみて、初項・第 $2$ 項から係数を連立して決める。重解の場合は形が変わる(そのときは別扱い)。

発展。 さらに視点を上げると、$\left(\genfrac{}{}{0ex}{}{a_{n+1}}{a_n}\right)$ を次々に送る線形変換とみたとき、特性方程式の $2$ 解 $2,3$ はその行列の固有値にあたる。

一般項が「固有値の $n$ 乗の重ね合わせ」になるのは、対角化して各固有方向に分けて考えられるからだ。

$3$ 項間にかぎらず、線形漸化式の一般項はいつでも特性方程式(固有方程式)の解で決まる。異なる解なら累乗の和、重解なら $n$ 倍の項がつく、という違いも固有値の重複度で説明できる。

別解

別解:$2$ 通りの因数分解で解く(特性方程式が何をしているか)。 特性方程式を暗記せずとも、漸化式そのものを因数分解すれば公比が見える。

$a_{n+2}=5a_{n+1}-6a_n$ は $a_{n+2}-2a_{n+1}=3(a_{n+1}-2a_n)$ と書ける。右辺を展開すると $3a_{n+1}-6a_n$ で、確かに一致する。これは「$a_{n+1}-2a_n$ が公比 $3$ の等比数列」を意味する。$b_n=a_{n+1}-2a_n$ とおくと $b_1=a_2-2a_1=2$ だから $b_n=2\cdot 3^{n-1}$。

同じ式を $a_{n+2}-3a_{n+1}=2(a_{n+1}-3a_n)$ とも因数分解できる。$c_n=a_{n+1}-3a_n$ とおくと $c_1=1$ で $c_n=2^{n-1}$。$2$ つの式を引き算すると $b_n-c_n=(a_{n+1}-2a_n)-(a_{n+1}-3a_n)=a_n$。よって

$$a_n=b_n-c_n=2\cdot 3^{n-1}-2^{n-1}.$$

特性方程式 $x^2=5x-6$ の $2$ 解 $2,3$ は、この $2$ 通りの因数分解の公比そのもの。だから「$2$ 解を公比とする等比の重ね合わせ」で一般項が書けた。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=2a_n+3^n$。もし右辺に $3^n$ がなければ、ただの公比 $2$ の等比数列だ。

その $3^n$ が邪魔で等比にならない。だが逆に、一般項にも $3^n$ の形の項が現れるはず、と予想できる。そこで $a_n=A\cdot 2^n+C\cdot 3^n$ とおく。$2^n$ が「等比のなごり(斉次解)」、$C\cdot 3^n$ が「$3^n$ に対応する分(特殊解)」。

漸化式に代入して $3^n$ の係数から $C$ を、初項から $A$ を決める。

① 特殊解を予想する。 $a_n=A\cdot 2^n+C\cdot 3^n$ とおき、漸化式 $a_{n+1}=2a_n+3^n$ に代入。$3^n$ の項に注目すると $C\cdot 3^{n+1}=2C\cdot 3^n+3^n$、すなわち $3C=2C+1$ より $C=1$。

② 初項で $A$ を決める。 $a_n=A\cdot 2^n+3^n$。$a_1=2A+3=1$ より $A=-1$。よって

$$a_n=-2^n+3^n=3^n-2^n$$

(検算:$a_1=3-2=1$、$a_2=9-4=5$。漸化式 $a_2=2\cdot 1+3^1=5$ と一致。)

まとめ:$q^n$ を含む漸化式は「特殊解 $C\cdot q^n$ を予想 + 斉次解 $A\cdot p^n$」。$3^n$ の係数を合わせて $C=1$、初項で $A=-1$。両辺を $3^{n+1}$ で割って $\frac{a_{n+1}}{3^{n+1}}$ の漸化式にする別法でも同じ答え。

発展。 $a_{n+1}=p{a}_n+q^n$ 型の一般項は、公比 $p$ と $q$ の $2$ つの等比の差や和になる。今回の $3^n-2^n$ もその形だ。

もし $p=q$(たとえば $a_{n+1}=2a_n+2^n$)なら、特殊解が斉次解と同じ公比とぶつかる。すると $n\cdot 2^n$ のような「$n$ 倍」の項が現れる。

これは振り子に固有振動数と同じリズムの力を加えると振幅が育つ「共鳴」と同じ構造だ。漸化式と微分方程式は、離散と連続の違いだけで、解の作り方(斉次解 $+$ 特殊解)がそっくり対応している。

別解

別解:小さい項を書き出して見抜く(苦手な人向けの実験ルート)。 特殊解を予想するのが不安なら、まず数項を手で計算して規則を探す。

$a_1=1$、$a_2=2\cdot 1+3=5$、$a_3=2\cdot 5+9=19$、$a_4=2\cdot 19+27=65$。並べると $1,5,19,65$。それぞれ $3^n$ と $2^n$ を書き出すと、$3-2=1$、$9-4=5$、$27-8=19$、$81-16=65$。ぴたりと合う。つまり $a_n=3^n-2^n$ と予想できる。確かめは漸化式への代入で十分で、$3^{n+1}-2^{n+1}=2(3^n-2^n)+3^n$ を整理すると $3\cdot 3^n-2\cdot 2^n=3\cdot 3^n-2\cdot 2^n$ と成り立つ。

係数比較で特殊解を作る本解と同じ答え。実験で当たりをつけ、あとで代入して確かめる流れは、型を忘れたときの保険になる。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=\frac{a_n}{2a_n+1}$ は、分子・分母の両方に $a_n$ がいて、そのままでは手がつかない。

分数型の漸化式は「逆数をとる」と急に簡単になることが多い。$\frac{1}{a_{n+1}}$ を作ってみるのが第一手。計算すると $\frac{2a_n+1}{a_n}=2+\frac{1}{a_n}$。$\frac{1}{a_n}$ で見ると、ただの等差数列になっている。

そこで $b_n=\frac{1}{a_n}$ とおいて等差数列として解き、最後に逆数を戻す。

① 逆数をとる。

$$\frac{1}{a_{n+1}}=\frac{2a_n+1}{a_n}=2+\frac{1}{a_n}$$

$b_n=\frac{1}{a_n}$ とおくと

$$b_{n+1}=b_n+2$$

② 等差数列を解く。 $b_1=\frac{1}{a_1}=1$、公差 $2$ の等差数列だから

$$b_n=1+2(n-1)=2n-1$$

③ $a_n$ に戻す。

$$a_n=\frac{1}{b_n}=\frac{1}{2n-1}$$

(検算:$a_1=1$、$a_2=\frac{1}{2\cdot 1+1}=\frac{1}{3}=\frac{1}{2\cdot 2-1}$。)

まとめ:分数型は「逆数をとって等差(または等比)型に」。$\frac{1}{a_{n+1}}=2+\frac{1}{a_n}$ となり、$b_n=\frac{1}{a_n}$ が公差 $2$ の等差。最後に逆数を戻して $a_n=\frac{1}{2n-1}$。

発展。 逆数で線形になるのは偶然ではない。$a_{n+1}=\frac{a_n}{2a_n+1}$ は分数一次変換(メビウス変換)で、この種の変換は $2\times 2$ 行列の積に対応する。

分母の定数がちょうど $1$ だから逆数が等差になったが、一般の $\frac{\alpha a_n+\beta }{\gamma a_n+\delta }$ 型も、逆数や一次分数の置き換えで線形漸化式になる。連分数の理論もこの延長にある。分数の漸化式を見たら「逆数」「行列」を思い出すと道が拓ける。

別解

別解:数項を書き出して規則を見つける(苦手な人向けの実験ルート)。 逆数の変形を思いつかなくても、最初の数項を計算すれば形が見える。

$a_1=1$。$a_2=\frac{1}{2\cdot 1+1}=\frac{1}{3}$。$a_3=\frac{1/3}{2/3+1}=\frac{1/3}{5/3}=\frac{1}{5}$。$a_4=\frac{1/5}{2/5+1}=\frac{1/5}{7/5}=\frac{1}{7}$。

並べると $1,\frac{1}{3},\frac{1}{5},\frac{1}{7},\dots$。分母が $1,3,5,7$ と奇数で並ぶ。つまり $a_n=\frac{1}{2n-1}$ と予想できる。逆数 $b_n=2n-1$ が公差 $2$ の等差になっているのが、逆数変換のうまくいく理由。

分母だけ見れば規則は一目瞭然。実験で答えを見抜き、逆数変換でその裏づけをとる、という順でも解ける。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=2a_n+n$。右辺の $n$ さえなければ公比 $2$ の等比数列だ。

その $n$($1$ 次式)が加わったぶん、一般項にも $1$ 次式の項が現れると予想する。そこで $a_n=A\cdot 2^n+pn+q$ とおく。$A\cdot 2^n$ が等比のなごり(斉次解)、$pn+q$ が $n$ に対応する分(特殊解)。漸化式に代入し、$n$ の係数と定数を合わせて $p,q$ を、初項で $A$ を決める。

① 特殊解を予想する。 $a_n=A\cdot 2^n+pn+q$ とおき、$a_{n+1}=2a_n+n$ に代入する。$1$ 次式の部分だけ見ると

$$p(n+1)+q=2(pn+q)+n$$

$n$ の係数:$p=2p+1$ より $p=-1$。定数:$p+q=2q$ より $q=p=-1$。よって特殊解は $-n-1$。

② 初項で $A$ を決める。 $a_n=A\cdot 2^n-n-1$。$a_1=2A-2=1$ より $A=\frac{3}{2}$。よって

$$a_n=\frac{3}{2}\cdot 2^n-n-1=3\cdot 2^{n-1}-n-1$$

(検算:$a_1=3-2=1$、$a_2=6-3=3$。漸化式 $a_2=2\cdot 1+1=3$ と一致。)

まとめ:$1$ 次式を含む漸化式は「特殊解を $1$ 次式 $\alpha n+\beta$ で予想 + 斉次解 $A\cdot p^n$」。係数比較で $p=-1,q=-1$、初項で $A=\frac{3}{2}$。$\frac{3}{2}\cdot 2^n=3\cdot 2^{n-1}$ と整えるときれい。

発展。 右辺に加わるもの(非斉次項)が $k$ 次式なら、特殊解も $k$ 次式でおくのが原則。$3^n$ なら $C\cdot 3^n$、$n$ なら $pn+q$、$n^2$ なら $2$ 次式、という具合だ。

ただし例外がある。非斉次項が斉次解と同じ形($a_{n+1}=2a_n+2^n$ の $2^n$ など)のときは、特殊解の次数を $1$ つ上げる。ここでも「共鳴」が起きる。

この「斉次解 $+$ 特殊解」「非斉次項の形に合わせて特殊解をおく」枠組みは、線形微分方程式とまったく同じ。離散版の未定係数法だ。

別解

別解:階差をとって $n$ を消す(得意な人向けの視点)。 特殊解を予想せずとも、$1$ 個ずらして引けば厄介な $n$ が消せる。

$a_{n+1}=2a_n+n$ の添字を $1$ つ上げた $a_{n+2}=2a_{n+1}+(n+1)$ から、もとの式を引く。

$$a_{n+2}-a_{n+1}=2(a_{n+1}-a_n)+1.$$

$c_n=a_{n+1}-a_n$(階差)とおくと $c_{n+1}=2c_n+1$。これは特性方程式型で、$c_n+1=2(c_{n-1}+1)$ と等比化できる。$c_1=a_2-a_1=3-1=2$ だから $c_n+1=3\cdot 2^{n-1}$、すなわち $c_n=3\cdot 2^{n-1}-1$。これを初項に積み上げると

$$a_n=a_1+\sum _{k=1}^{n-1}{c}_k=1+3(2^{n-1}-1)-(n-1)=3\cdot 2^{n-1}-n-1.$$

特殊解を予想する本解と同じ。$1$ 次式が残って扱いにくいなら「ずらして引いて消す」のもよく使う一手だ。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=a_n+2b_n$、$b_{n+1}=2a_n+b_n$。$a$ と $b$ を入れ替えても形が変わらない、対称な連立だ。

対称な連立漸化式は「和 $a_n+b_n$」と「差 $a_n-b_n$」を作ると、互いの絡みがほどける。実際、$2$ 式を足すと $a_n+b_n$ だけの式、引くと $a_n-b_n$ だけの式になり、どちらも単独の等比数列。和と差をそれぞれ解いてから、$a_n,b_n$ を復元する。

① 和と差を作る。 $2$ 式を足すと

$$a_{n+1}+b_{n+1}=3a_n+3b_n=3(a_n+b_n)$$

$2$ 式を引くと

$$a_{n+1}-b_{n+1}=-a_n+b_n=-(a_n-b_n)$$

② それぞれ等比数列として解く。 $s_n=a_n+b_n$ は初項 $s_1=1$、公比 $3$ で $s_n=3^{n-1}$。$d_n=a_n-b_n$ は初項 $d_1=1$、公比 $-1$ で $d_n=(-1{)}^{n-1}$。

③ 復元する。

$$a_n=\frac{s_n+d_n}{2}=\frac{3^{n-1}+(-1{)}^{n-1}}{2},b_n=\frac{s_n-d_n}{2}=\frac{3^{n-1}-(-1{)}^{n-1}}{2}$$

(検算:$a_1=\frac{1+1}{2}=1$、$b_1=\frac{1-1}{2}=0$。)

まとめ:対称な連立漸化式は「和と差で単独化」。和は公比 $3$、差は公比 $-1$ の等比になり、$a_n=\frac{s_n+d_n}{2}$、$b_n=\frac{s_n-d_n}{2}$ で復元。和・差が両方きれいに等比になるのが対称形の強み。

発展。 この連立は $\left(\genfrac{}{}{0ex}{}{a_{n+1}}{b_{n+1}}\right)=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)\left(\genfrac{}{}{0ex}{}{a_n}{b_n}\right)$ と行列で書ける。

行列 $\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$ の固有値は $3$ と $-1$、固有ベクトルは $(1,1)$ と $(1,-1)$。この $(1,1)$ 方向が「和」、$(1,-1)$ 方向が「差」にあたる。「和と差でほどける」のは偶然ではなく、固有ベクトルの方向を見ていたことになる。連立漸化式は行列の固有値・固有ベクトルで一般項が決まる。

別解

別解:$1$ 文字消して $3$ 項間漸化式にする(得意な人向けの視点)。 和と差を思いつかなくても、$b_n$ を消せば見慣れた $3$ 項間漸化式になる。

第 $1$ 式から $b_n=\frac{a_{n+1}-a_n}{2}$。これを第 $2$ 式 $b_{n+1}=2a_n+b_n$ に代入する。$\frac{a_{n+2}-a_{n+1}}{2}=2a_n+\frac{a_{n+1}-a_n}{2}$ を整理して

$$a_{n+2}=2a_{n+1}+3a_n.$$

特性方程式 $x^2=2x+3$、すなわち $(x-3)(x+1)=0$ より $x=3,-1$。よって $a_n=A\cdot 3^{n-1}+B\cdot (-1{)}^{n-1}$。$a_1=1$、$a_2=a_1+2b_1=1$ から $A+B=1$、$3A-B=1$。これを解くと $A=B=\frac{1}{2}$、$a_n=\frac{3^{n-1}+(-1{)}^{n-1}}{2}$。$b_n=\frac{a_{n+1}-a_n}{2}$ で $b_n$ も出る。

和と差でほどく本解と同じ。$1$ 文字消去は対称でない連立にも使える汎用の手だ。

方針

解答

⓪ 発想(どう考え始めるか) 「$n\ge 5$ のすべてで $2^n>n^2$」という主張は、数学的帰納法で示す。

決め手は $n=k$ の仮定 $2^k>k^2$ を、$n=k+1$ の $2^{k+1}>(k+1{)}^2$ につなぐことだ。$2^{k+1}=2\cdot 2^k$ に仮定を使えば $2^{k+1}>2k^2$ まで進める。あとは $2k^2\ge (k+1{)}^2$ が言えれば、間に挟んで目標に届く。だから「$2k^2$ と $(k+1{)}^2$ の大小」という補助の不等式を先に用意しておく。

① 出発点。 $n=5$ のとき $2^5=32$、$5^2=25$ で $32>25$。成立。

② 仮定と橋渡しの準備。 $n=k$($k\ge 5$)で $2^k>k^2$ が成り立つと仮定する。まず補助的に、$k\ge 3$ のとき $2k^2\ge (k+1{)}^2$ を示す。差をとると

$$2k^2-(k+1{)}^2=k^2-2k-1=(k-1{)}^2-2$$

$k\ge 3$ なら $(k-1{)}^2\ge 4>2$ なので $2k^2-(k+1{)}^2>0$、すなわち $2k^2>(k+1{)}^2$。

③ $n=k+1$ を導く。 仮定より $2^{k+1}=2\cdot 2^k>2\cdot k^2=2k^2$。さらに②($k\ge 5\ge 3$)より $2k^2>(k+1{)}^2$。よって

$$2^{k+1}>2k^2>(k+1{)}^2$$

$n=k+1$ でも成立。

④ 結論。 (i)(ii) より、$n\ge 5$ のすべての自然数 $n$ で $2^n>n^2$。(証明終)

まとめ:指数 vs 多項式の不等式は帰納法で、$2^{k+1}=2\cdot 2^k$ に仮定を使い、$2k^2$ を経由して $(k+1{)}^2$ に橋渡し。$2k^2>(k+1{)}^2$($k\ge 3$)を補助的に示すのが要。$n=4$ では $16=16$ と等号で、$n\ge 5$ が条件になっている。

発展。 指数関数はどんな多項式もいずれ追い抜く。$2^n$ と $n^2$ の場合、$n=2$ で $4=4$、$n=4$ で $16=16$ と $2$ 度並び、$n\ge 5$ で $2^n$ のほうがずっと大きくなる。

境界の $n=4$ で等号になるからこそ、条件が $n\ge 5$ になっている。$n=3$ では $8<9$ とまだ多項式が勝つ点にも注意。一般に $a>1$ なら $\frac{a^n}{n^k}\to \infty$。対数をとると $n\log a-k\log n\to \infty$ からも分かる。指数の伸びは多項式より一段速い。

別解

別解:比 $\frac{2^n}{n^2}$ が増えることを示す(得意な人向けの視点)。 補助不等式を毎回作る代わりに、比の増減でまとめて片づける。

$r_n=\frac{2^n}{n^2}$ とおくと

$$\frac{r_{n+1}}{r_n}=\frac{2^{n+1}}{(n+1{)}^2}\cdot \frac{n^2}{2^n}=\frac{2}{{\left(1+\frac{1}{n}\right)}^2}.$$

$n\ge 3$ なら $1+\frac{1}{n}\le \frac{4}{3}$ で ${\left(1+\frac{1}{n}\right)}^2\le \frac{16}{9}<2$。よって $\frac{r_{n+1}}{r_n}>1$、つまり $r_n$ は $n\ge 3$ で増え続ける。出発点は $r_5=\frac{32}{25}>1$。増加数列だから $n\ge 5$ では $r_n\ge r_5>1$、すなわち $2^n>n^2$。

帰納法の橋渡しと中身は同じで、${\left(1+\frac{1}{n}\right)}^2<2$ は $2k^2>(k+1{)}^2$ と同じ主張。比の単調性で見ると、なぜ一度上回るとその後もずっと上回るのかが、直感的につかめる。

方針

解答

⓪ 発想(どう考え始めるか) 「すべての自然数 $n$ で $n^3+2n$ が $3$ の倍数」を帰納法で示す。

倍数の帰納法では、$n=k+1$ の式と $n=k$ の式の「差」を作るのが基本だ。$(k+1{)}^3+2(k+1)$ から $k^3+2k$ を引くと、うまく $3$ でくくれる形が出るはず。その差が $3$ の倍数なら、仮定「$k$ の式が $3$ の倍数」に足して、$k+1$ の式も $3$ の倍数になる。

① 出発点。 $n=1$ のとき $1^3+2\cdot 1=3$。$3$ の倍数。

② 仮定と差。 $n=k$ で $k^3+2k$ が $3$ の倍数と仮定する。$n=k+1$ の式との差を計算する。

$$\{(k+1{)}^3+2(k+1)\}-(k^3+2k)=(k^3+3k^2+3k+1+2k+2)-(k^3+2k)$$ $$=3k^2+3k+3=3(k^2+k+1)$$

これは $3$ の倍数。

③ $n=k+1$ を導く。 よって

$$(k+1{)}^3+2(k+1)=\underset{3\text{の倍数(仮定)}}{\underbrace{(k^3+2k)}}+\underset{3\text{の倍数}}{\underbrace{3(k^2+k+1)}}$$

$3$ の倍数どうしの和だから $3$ の倍数。$n=k+1$ でも成立。

④ 結論。 (i)(ii) より、すべての自然数 $n$ で $n^3+2n$ は $3$ の倍数。(証明終)

まとめ:倍数の帰納法は「$k+1$ の式 $-$ $k$ の式 $=$ $3$ の倍数」を示す。差 $3(k^2+k+1)$ が $3$ でくくれれば、仮定に足して $k+1$ でも $3$ の倍数。差をとるのが計算のコツ。

発展。 じつは帰納法を使わずとも、$n^3+2n=n^3-n+3n=(n-1)n(n+1)+3n$ と変形すれば一目で分かる。連続 $3$ 整数の積は必ず $3$ の倍数、$3n$ も $3$ の倍数だからだ。

背景にあるのはフェルマーの小定理。素数 $p$ について $n^p\equiv n(\mathrm{mod}p)$ が成り立ち、$p=3$ なら $n^3\equiv n$、つまり $n^3-n$ は $3$ の倍数。$n^3+2n=(n^3-n)+3n$ と見れば、フェルマーの小定理そのものを使っている。倍数の証明は帰納法・因数分解・合同式のどれでも攻められる。

別解

別解:$3$ 連続整数の積に変形する(得意な人向けの直接証明)。 帰納法を使わず、式変形だけで示せる。

$$n^3+2n=n^3-n+3n=n(n^2-1)+3n=(n-1)n(n+1)+3n.$$

$(n-1)n(n+1)$ は連続する $3$ つの整数の積。連続 $3$ 整数には必ず $3$ の倍数が $1$ つ含まれるので、この積は $3$ の倍数。残りの $3n$ も当然 $3$ の倍数。$3$ の倍数どうしの和だから $n^3+2n$ は $3$ の倍数。

念のため合同式でも確かめられる。$n\equiv 0,1,2(\mathrm{mod}3)$ で $n^3+2n$ を計算すると、順に $0$、$1+2=3\equiv 0$、$8+4=12\equiv 0$。どの場合も $3$ の倍数。帰納法・因数分解・余りの分類、どれでも同じ結論にたどり着く。

方針

解答

⓪ 発想(どう考え始めるか) 領域の数を直接数えるのは大変。そこで「直線を $1$ 本増やすと領域がいくつ増えるか」を漸化式にする。

$n$ 本目の直線を引くとき、既存の $n-1$ 本と何回交わるかを考える。どの $2$ 本も平行でなく、$3$ 本が $1$ 点に集まらないので、交点はちょうど $n-1$ 個。その $n-1$ 個の交点で、$n$ 本目自身は $n$ 個の部分(線分や半直線)に切り分けられる。

各部分は通り抜ける領域を $2$ つに割る。つまり領域が $n$ 個増える、と見通せる。

① 漸化式を立てる。 $n$ 本目の直線は既存 $n-1$ 本と $n-1$ 個の交点をもち、それらで $n$ 個の線分・半直線の部分に分かれる。各部分が通る領域を $1$ つずつ $2$ 分割するので、領域は $n$ 個増える。よって

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

初項は、直線 $1$ 本で平面が $2$ 分割されるから $a_1=2$。

② 階差型として解く。 $n\ge 2$ で

$$a_n=a_1+\sum _{k=2}^{n}k=2+\left(\frac{n(n+1)}{2}-1\right)=1+\frac{n(n+1)}{2}$$

③ 確認。 $a_1=1+1=2$、$a_2=1+3=4$、$a_3=1+6=7$。実際、$2$ 本で $4$ 領域、$3$ 本で $7$ 領域。一致する。

まとめ:図形の領域数は「$1$ 本増やすと領域がいくつ増えるか」を漸化式に。$n$ 本目は $n-1$ 交点で $n$ 部分に分かれ、領域が $n$ 個増える($a_n=a_{n-1}+n$)。階差型を解いて $a_n=1+\frac{n(n+1)}{2}$。

発展。 答え $1+\frac{n(n+1)}{2}$ は、じつは $\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ に等しい($1+n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ と展開すると分かる)。

この $1,n,\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ は、それぞれ「平面全体」「直線が単独で作る境界」「$2$ 直線の交点」の寄与。$2$ 直線から交点が $1$ つ決まるので、交点数が $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ になる。

平面を空間($3$ 次元)に上げ、$n$ 枚の平面で分けるときは $\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\left(\genfrac{}{}{0ex}{}{n}{3}\right)$。次元を上げるほど二項係数の和が伸びる、という規則だ。

別解

別解:交点の個数から直接数える(得意な人向けの視点)。 漸化式を経由せず、「領域数 $=1+$(直線の本数)$+$(交点の個数)」という公式ですぐに出せる。

まず平面全体で領域は $1$ 個。直線を $1$ 本ずつ足すと、新たな交点ができるたびに領域が余分に $1$ つ増える。整理すると、最終的な領域数は

$$a_n=1+n+(\text{交点の個数}).$$

交点は「どの $2$ 本を選ぶか」で $1$ つ決まるから、$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$ 個。よって

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

漸化式を解く本解と同じ結果。$n=3$ なら $1+3+3=7$ 領域で一致する。「直線の寄与 $n$」と「交点の寄与 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$」を分けて数えるのがこの見方のコツ。