漸化式と数学的帰納法 ★ 基礎の問題 全12問

方針

解答

⓪ 発想(どう考え始めるか) 漸化式とは「次の項の作り方」を書いたルールブックだ。

$a_{n+1}=a_n+3$ は、今の項に $3$ を足すと、次の項になると言っている。まず、実際に作ってみよう。

$$2,5,8,11,14,\dots$$

$3$ ずつ増えている。これは等差数列そのものだ。漸化式を見たら、まず「どの基本型か」を判定する。足すのか、掛けるのか。 ここでは足しているので、等差。

知っている数列に直せれば、あとは公式に当てはめるだけだ。 これがこの単元すべての出発点である。

① 型を見抜く。 $a_{n+1}=a_n+3$ は「毎回 $3$ 足す」ので、公差 $3$ の等差数列。

② 一般項を書く。 初項 $2$、公差 $3$。

$$a_n=2+(n-1)\times 3=3n-1$$

まとめ:$a_{n+1}=a_n+(\text{定数})$ を見たら等差数列。公差はその定数。漸化式の一番やさしい型で、等差の一般項の公式に入れるだけだ。

発展。 漸化式はたかが「次の項の作り方」だ。だが、この方法は現代科学でも広く使われている。

自然現象を表す式はたいてい「変化のルール」の形をしている。

• 物体の運動: 今の速度から、次の瞬間の位置が決まる
• 人口: 今の人口から、来年の人口が決まる
• 気温: 今の状態から、$1$ 分後の状態が決まる

「今の状態 → 次の状態」 という形は、漸化式と同じだ。連続的に扱えば微分方程式になる。

$$\frac{da}{dn}=3⟺a_{n+1}-a_n=3$$

左は微分方程式、右は漸化式。 言っていることは同じで、変化率が $3$ で一定である。そして解も同じ形になる。

$$a(n)=3n+C{a}_n=3n-1$$

コンピュータは微分方程式をそのままでは解けない。 だから漸化式に直して、$1$ ステップずつ計算する。これをオイラー法という。

$$a_{\text{next}}=a_{\text{now}}+(\text{変化率})\times (\text{刻み幅})$$

天気予報も、ロケットの軌道計算も、ゲームの物理エンジンも、この $1$ 行を何百万回も繰り返している。

$a_{n+1}=a_n+3$。 この素朴な式は現象をコンピュータで再現する方法の、いちばん簡単な例である。

別解

公式を思い出せないときは、「グラフにする」と分かる。

項を書き出し、点として打つ。 横軸に番号 $n$、縦軸に値 $a_n$ をとる。

$$(1,2),(2,5),(3,8),(4,11),(5,14),\dots$$

この $5$ 点は一直線に並ぶ。 $1$ 進むごとに、必ず $3$ 上がるからだ。直線なら、式は $1$ 次式である。

$$a_n=3n+c$$

傾き $3$ は「$1$ 進むと $3$ 増える」こと、つまり公差そのものだ。あとは切片 $c$ を決めればよい。$n=1$ のとき $a_1=2$ だから

$$3\times 1+c=2⟹c=-1$$

$$a_n=3n-1$$

公式と同じ答えが出た。

確かめる。 $n=1$ で $2$、$n=4$ で $11$

この見方の利点。 「$a_n=a_1+(n-1)d$ の $n-1$ は $n$ だったか?」と迷わずに済む。直線の式を立てて、$1$ 点通せばいいだけだ。

そして、この見方は数列の性質をよく表している。等差数列 $=$ $1$ 次関数の、飛び飛びの値。

$$y=3x-1\text{の }x=1,2,3,\dots \text{ だけを見たもの}$$

公差 $=$ 傾き。 この対応を覚えておくと、等差数列の問題は「直線の問題」として読める。たとえば「第 $5$ 項が $14$、第 $9$ 項が $26$ の等差数列」なら、$2$ 点 $(5,14)$、$(9,26)$ を通る直線を求めればよい。傾きは

$$\frac{26-14}{9-5}=3$$

公差 $3$ が $2$ 点の傾きとして出てくる。

方針

解答

⓪ 発想(どう考え始めるか) 前問は「足す」型だった。今度は $a_{n+1}=2a_n$ で、「掛ける」型だ。

書き出してみる。

$$3,6,12,24,48,\dots$$

毎回 $2$ 倍。これは等比数列である。漸化式の第一関門はこの $2$ 択だ。

• $a_{n+1}=a_n+d$ → 足す → 等差
• $a_{n+1}=r{a}_n$ → 掛ける → 等比

$+$ か $\times$ か。 ここを見誤らなければ、あとは公式に乗せるだけである。

① 型を見抜く。 $a_{n+1}=2a_n$ は「毎回 $2$ 倍」なので、公比 $2$ の等比数列。

② 一般項を書く。 初項 $3$、公比 $2$。

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

まとめ:$a_{n+1}=r\cdot a_n$ を見たら等比数列。公比はその $r$。等比の一般項に入れるだけだ。

発展。 「毎回 $2$ 倍」は $1$ 行で書けるルールだ。しかし、その増え方は人間の直感を裏切る。

有名な逸話がある。

チェス盤の $1$ マス目に米を $1$ 粒、$2$ マス目に $2$ 粒、$3$ マス目に $4$ 粒と、前のマスの $2$ 倍を置いていく。$64$ マス目には何粒か。

$$a_n=2^{n-1}{a}_{64}=2^{63}$$

全部の合計は

$$1+2+4+\cdots +2^{63}=2^{64}-1=18,446,744,073,709,551,615$$

約 $1844$ 京粒。 重さにすると数千億トンで、世界で数千年かけて作る米の総量を超える。

「毎回 $2$ 倍」を $64$ 回繰り返すだけで、こうなる。

なぜ直感が外れるのか。 人間の感覚は足し算的にできている。「$1$ 日 $1$ 万円ずつ増える」なら $1$ 年で $365$ 万円と見当がつく。

だが掛け算的な増加は、$1$ 桁ずつ桁が増えていく。$n$ が線形に増えると、桁数が線形に増える。つまり値そのものは急激に大きくなる。

$$2^{10}\approx 10^3,2^{20}\approx 10^6,2^{30}\approx 10^9$$

$10$ 回倍にするごとに、約 $1000$ 倍。この感覚はふだんの生活でも役に立つ。

• 複利: 年利 $7\%$ なら約 $10$ 年で $2$ 倍($72$ の法則)
• 感染症: $1$ 人が $2$ 人にうつせば、$10$ 世代で $1000$ 人超
• 半導体: 「$2$ 年で $2$ 倍」(ムーアの法則)を $50$ 年続けた結果が、今のスマホだ

$a_{n+1}=2a_n$。 この $1$ 行が急激な増え方を生んでいる。

別解

公式を使わず、「$2$ を何回掛けたか」を数える。漸化式 $a_{n+1}=2a_n$ を、$a_n$ から順にさかのぼってみよう。

$$a_n=2a_{n-1}$$

その $a_{n-1}$ も $2a_{n-2}$ である。代入する。

$$a_n=2\cdot (2a_{n-2})=2^2{a}_{n-2}$$

もう一度。

$$a_n=2^2\cdot (2a_{n-3})=2^3{a}_{n-3}$$

規則が見える。

$$a_n=2^k{a}_{n-k}$$

$k$ 回さかのぼると、$2$ が $k$ 個出る。

どこまでさかのぼる? 分かっているのは $a_1$ だけだから、$a_1$ まで。

$$n-k=1⟹k=n-1$$

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

公式と同じ答え。

この方法の利点は、$n-1$ という指数が「数えた結果」として出てくることだ。公式を丸暗記していると「$r^n$ だったか $r^{n-1}$ だったか」で必ず迷う。しかしさかのぼって数えれば、迷いようがない。

具体例で確かめる。 $a_5$ は?

$$a_5\to a_4\to a_3\to a_2\to a_1$$

矢印は $4$ 本。 つまり $2$ 倍を $4$ 回。

$$a_5=3\times 2^4=48$$

第 $5$ 項までに、$2$ 倍は $4$ 回。 初項はまだ $1$ 度も掛けられていないからだ。

これは「植木算」と同じ構造である。 木が $5$ 本並ぶとき、木と木のあいだは $4$ か所。項が $n$ 個なら、掛け算は $n-1$ 回。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=a_n+2n$ は足し算だが、足す量が毎回変わる。

$$a_{n+1}-a_n=2n$$

$n=1$ なら $2$、$n=2$ なら $4$、$n=3$ なら $6$ を足す。足す量そのものが数列になっている。

これを階差型という。

$$1\stackrel{+2}{\to }3\stackrel{+4}{\to }7\stackrel{+6}{\to }13\stackrel{+8}{\to }21$$

差が分かっているなら、初項から順に足し上げれば一般項に戻せる。

$$a_n=a_1+(\text{1 回目の差})+(\text{2 回目の差})+\cdots$$

注意すべきは「何回足すか」だ。 $a_1$ から $a_n$ までは、矢印が $n-1$ 本。だから足す差も $n-1$ 個で、和の上端は $n-1$ になる。

「差が分かれば、和で戻す。ただし上端は $n-1$。」 これが階差型の解き方である。

① 階差を確かめる。 $a_{n+1}-a_n=2n$ なので階差は $f(n)=2n$。

② 和で一般項を出す($n\geqq 2$)。 上端は $n-1$。

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

③ $n=1$ を確認する。 $a_1=1^2-1+1=1$ で一致。すべての $n$ で成り立つ。

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

まとめ:$a_{n+1}=a_n+(n\text{ の式})$ は階差型。「初項 + 階差の和」で一般項が出る。和の上端が $n-1$ なのと、$n=1$ の確認を忘れずに。

発展。 出てきた一般項 $a_n=n^2-n+1$ には、よく似た有名な式がある。

定数を $1$ から $41$ に変えてみる。

$$f(n)=n^2-n+41$$

$n$ に $1$ から順に入れてみよう。

$$f(1)=41,f(2)=43,f(3)=47,f(4)=53,f(5)=61$$

$41,43,47,53,61$ は、すべて素数だ。偶然だろうか。続けてみる。

$$71,83,97,113,131,151,173,197,223,\dots$$

これも全部、素数。

実は、$n=1$ から $n=40$ まで、$40$ 個すべてが素数になる。 オイラーが $1772$ 年に見つけた、有名な素数生成多項式である。では、$n=41$ は?

$$f(41)=41^2-41+41=41^2=1681$$

$41\times 41$ なので、素数ではない。

あっけない終わり方だ。 だが、この失敗こそが教訓になる。$40$ 回連続で成り立っても、それは証明ではない。

「$n=1$ から $n=40$ まで確かめたから、すべての $n$ で正しい」という推論は誤りである。

では、どうすればすべての $n$ で言えるのか。 そのための道具がこの単元の後半で学ぶ数学的帰納法だ。「$1$ 個目が正しい」+「$k$ 個目が正しければ $k+1$ 個目も正しい」という、この $2$ 段があって初めて、無限個を保証できる。

実験は予想を生む。証明が予想を確定する。 オイラーの $41$ はその境目を示している。

ちなみに、すべての $n$ で素数になる多項式は存在しない(定数を除く)。これは証明されている。素数はそんなに簡単な式では捕まらない。

別解

「答えの形」を先に予想して、係数だけ決める。まず、次数を見積もる。階差(足す量)は $2n$ で、$1$ 次式だ。

和をとると、次数は $1$ 上がる。

$$\sum _{k=1}^{n}k=\frac{n(n+1)}{2}(1\text{ 次の和}\to 2\text{ 次})$$

だから一般項は $2$ 次式のはずである。そこで、こう置く。

$$a_n=A{n}^2+Bn+C$$

$A$、$B$、$C$ を、条件から決める。

① 漸化式に代入する。 $a_{n+1}-a_n=2n$ に入れる。

$$a_{n+1}=A(n+1{)}^2+B(n+1)+C$$

$$a_{n+1}-a_n=A\{(n+1{)}^2-n^2\}+B\{(n+1)-n\}=A(2n+1)+B$$

これが $2n$ に等しい。

$$2An+(A+B)=2n+0$$

② 係数を比べる。 すべての $n$ で成り立つのだから、$n$ の係数どうし、定数どうしが等しい。

$$2A=2⟹A=1$$ $$A+B=0⟹B=-1$$

③ 初項で $C$ を決める。 $a_1=1$ より

$$A+B+C=1⟹1-1+C=1⟹C=1$$

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

本解と同じ答え。

確かめる。 $n=1,2,3,4$ で $1,3,7,13$

この方法の強み。 $\Sigma$ の計算をまったくしていない。形を仮定して、係数を合わせるだけで済んでいる。

未定係数法と呼ばれるこの手は、階差が多項式のときにいつでも使える。

• 階差が $1$ 次式 → 一般項は $2$ 次式
• 階差が $2$ 次式 → 一般項は $3$ 次式

$\Sigma$ の公式を思い出せなくても、連立方程式さえ解ければ答えにたどり着く。

ただし、階差が $2^n$ のような指数のときは使えない。 そのときは素直に $\Sigma$ で足し上げる。道具は使い分けるものだ。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=2a_n+1$ は、掛けてから、さらに足している。

等差でも等比でもない。だが、書き出すと規則が分かる。

$$1,3,7,15,31,63,\dots$$

各項に $1$ を足してみよう。

$$2,4,8,16,32,64,\dots$$

$2$ の累乗になった。

つまり $a_n+1$ は等比数列である。$1$ だけずらすと、等比になる。

なぜ $1$ なのか。 その $1$ を機械的に見つける道具が特性方程式だ。$\alpha =2\alpha +1$ を解くと $\alpha =-1$。この $\alpha$ を引く($=1$ を足す)と、余計な定数が消える。

「ズレを吸収して等比にする」のが特性方程式型の解き方である。

① 特性方程式を解く。 $\alpha =2\alpha +1$ より $\alpha =-1$。

② $\alpha$ を引いて等比の形にする。

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

③ 置きかえて等比数列にする。 $b_n=a_n+1$ とおくと $b_{n+1}=2b_n$。初項 $b_1=a_1+1=2$。

$$b_n=2\cdot 2^{n-1}=2^n$$

④ $a_n$ に戻す。 $a_n=b_n-1$。

$$a_n=2^n-1$$

まとめ:$a_{n+1}=p{a}_n+q$($p\ne 1$)は「特性方程式で $\alpha$ を出す → $a_n-\alpha$ を等比数列とみる」。$\alpha$ は「動かない値(不動点)」で、そこからのズレが等比的に変化する、というイメージだ。

発展。 $a_n=2^n-1$ という数列は、パズルでも有名だ。

ハノイの塔。

$3$ 本の柱があり、$1$ 本目に大きさの違う円盤が $n$ 枚、大きい順に積んである。これを別の柱へ移す。ただし

• $1$ 回に動かせるのは $1$ 枚
• 小さい円盤の上に、大きい円盤を置いてはいけない

最小の手数は何回か。

$n$ 枚のときの最小手数を $h_n$ とする。 移す手順を考えると、必ずこうなる。

$$\underset{h_{n-1}\text{ 回}}{\underbrace{\text{上の }n-1\text{ 枚を、空いた柱へ}}}\to \underset{1\text{ 回}}{\underbrace{\text{最大の 1 枚を目的の柱へ}}}\to \underset{h_{n-1}\text{ 回}}{\underbrace{\text{n−1 枚を上に載せる}}}$$

$$h_n=2h_{n-1}+1$$

この問題の漸化式そのものだ。

$h_1=1$ だから

$$h_n=2^n-1$$

$3$ 枚なら $7$ 手、$10$ 枚なら $1023$ 手。

伝説によれば、インドの寺院に $64$ 枚の黄金の円盤があり、僧侶がこれを移し終えたとき世界が終わる、という。

$$h_{64}=2^{64}-1\approx 1.8\times 10^{19}$$

$1$ 秒に $1$ 手動かしても、約 $5850$ 億年かかる。 宇宙の年齢($138$ 億年)の $40$ 倍以上だ。移し終えるのは、はるか先のことになる。

この数列 $2^n-1$ はメルセンヌ数と呼ばれる。 $n$ が素数のとき $2^n-1$ も素数になることがあり、知られている最大の素数はすべてこの形をしている($2024$ 年時点の最大は $2^{136279841}-1$、$4100$ 万桁超)。

$a_{n+1}=2a_n+1$。 この短いルールから、パズルの手数と、知られている最大の素数の形の両方が出てくる。

別解

特性方程式を使わずに、「差をとって定数を消す」。

邪魔なのは、末尾の $+1$ だ。 この定数さえ消えれば、話は簡単になる。定数を消すときによく使う方法が「引き算」である。

漸化式を $2$ つ並べる。

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

辺々を引く。

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

$+1$ が消えた。 定数どうしが打ち消し合ったからだ。ここで、差を新しい数列と見る。

$$b_n=a_{n+1}-a_n$$

すると

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

$b_n$ は公比 $2$ の等比数列だ。

初項を求める。 $a_1=1$、$a_2=2\cdot 1+1=3$ だから

$$b_1=a_2-a_1=2$$

$$b_n=2\cdot 2^{n-1}=2^n$$

差が分かったので、階差型として復元する。 $n\geqq 2$ で

$$a_n=a_1+\sum _{k=1}^{n-1}{b}_k=1+\sum _{k=1}^{n-1}{2}^k$$

等比数列の和。

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

$$a_n=1+(2^n-2)=2^n-1$$

$n=1$ でも $2^1-1=1$ で合う

本解と同じ答えにたどり着いた。

$2$ つの道を比べてみる。

• 本解(特性方程式): ズレの基準点 $\alpha$ を見つけ、$a_n-\alpha$ を等比にする
• 別解(階差): $2$ 式を引いて定数を消し、差 $b_n$ を等比にする

どちらも「等比数列に持ち込む」点は同じ。 違うのは何を等比にするかだ。本解は「ズレ」、別解は「差」を等比にしている。

別解の強み。 特性方程式を覚えていなくても、定数が邪魔なら引き算で消すという一般的な発想だけで解ける。この発想は $3$ 項間漸化式など、もっと難しい型でも通用する。

方針

解答

⓪ 発想(どう考え始めるか) 聞かれているのは $a_4$ ひとつだけだ。

一般項を求める必要はない。漸化式は「次の項の作り方」なのだから、$a_1$ から順に $3$ 回進めば $a_4$ に着く。

$$a_1\to a_2\to a_3\to a_4$$

式を解くより、手を動かすほうが速い。「漸化式 $=$ 一般項を求めるもの」と決めつけない。有限個でよいなら、逐次計算で足りる。 この割り切りも立派な判断である。

注意は $1$ 点だけ。 $a_{n+1}=a_n+n$ の $n$ は、毎回変わる。$a_2$ を作るときは $n=1$、$a_3$ を作るときは $n=2$ なので、添字を取り違えないことだ。

$a_{n+1}=a_n+n$ に $n=1,2,3$ を順に入れる。

$$a_2=a_1+1=1+1=2$$

$$a_3=a_2+2=2+2=4$$

$$a_4=a_3+3=4+3=7$$

よって $a_4=7$。

まとめ:「第 $4$ 項だけ」なら、一般項を求めるより順に代入するのが速い。$a_{n+1}=a_n+n$ の $n$ に、$a_2$ を出すときは $1$、$a_3$ は $2$、と正しく合わせるのがポイント。

発展。 この数列 $1,2,4,7,11,16,\dots$ は、身近な問題にも現れる。

ケーキを直線で切る問題。

丸いケーキを、まっすぐ $1$ 回切ると $2$ 切れ。$2$ 回切ると、うまく切れば $4$ 切れ。$3$ 回では?

$1$ 回目の切り口と平行に切ると $4$ 切れにしかならない。だが、すでにある $2$ 本の切り口を両方またぐように切ると $7$ 切れになる。$n$ 回切ったときの最大の切れ数を $R_n$ とすると

$$R_0=1,R_1=2,R_2=4,R_3=7,R_4=11,\dots$$

この問題の数列と、ぴったり同じだ。なぜ漸化式が同じになるのか。$n$ 本目の直線を引くとき、既にある $n-1$ 本すべてと交わるように引くのが最大だ。すると新しい直線は $n-1$ 個の交点で区切られ、$n$ 個の区間に分かれる。

その $n$ 個の区間がそれぞれ既存の領域を $1$ つずつ $2$ 分割する。

$$R_n=R_{n-1}+n$$

「$n$ 本目を引くと、領域は $n$ 個増える」ことが、この問題の $a_{n+1}=a_n+n$ の意味である。

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

$10$ 回切れば、最大 $56$ 切れ。

同じ漸化式がまったく違う問題から現れる。 数学では、こうしたことがよくある。「$1$ ずつ増える量を足していく」という構造さえ同じなら、ケーキだろうと数列だろうと、答えは同じ式になる。

構造が同じなら、答えも同じ。 数学が「抽象」を大事にするのは、$1$ つ解けば全部解けるからである。

別解

一般項を求めてから、$n=4$ を代入する。遠回りに見えるが、「第 $100$ 項は?」と聞かれたら、こちらが必要になる。

① 階差型として解く。

$$a_{n+1}-a_n=n$$

階差は $f(n)=n$。$n\geqq 2$ で

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

② 検算する。

$$a_4=1+\frac{3\times 4}{2}=1+6=7$$

逐次計算と同じ答え。

この一般項の中身を見てみよう。

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

これは三角数だ。 点を三角形に並べたときの個数である。

$$1,3,6,10,15,\dots$$

つまり

$$a_n=1+(\text{三角数})$$

数列そのものを書き出すと

$$1,2,4,7,11,16,22,\dots$$

差が $1,2,3,4,\dots$ と $1$ ずつ増える数列である。どちらを使うか、の判断。

• $a_4$ だけ → 逐次計算($3$ 回の足し算で終わる)
• $a_{100}$ が欲しい → 一般項($99$ 回足すのは現実的でない)

$$a_{100}=1+\frac{99\times 100}{2}=1+4950=4951$$

逐次計算なら $99$ 回。一般項なら $1$ 行。「小さい $n$ なら手を動かす、大きい $n$ なら式を作る」という使い分けが、漸化式との正しい付き合い方だ。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}-a_n=4$ なので、差がいつでも $4$ で一定だ。

「差が一定」の数列を、何と呼んだか。 等差数列だ。

$$5\stackrel{+4}{\to }9\stackrel{+4}{\to }13\stackrel{+4}{\to }17\stackrel{+4}{\to }21$$

$a_{n+1}=a_n+4$ と書き直せば、いつもの形になる。

表現が変わっても、中身は同じ。 漸化式は

• $a_{n+1}=a_n+d$
• $a_{n+1}-a_n=d$

と、$2$ 通りの書き方をされる。移項しただけである。「差の形で来たら、まず移項してみる」とよい。見慣れた形に戻せば、あとは公式に乗せるだけだ。

① 型を見抜く。 $a_{n+1}-a_n=4$(差が一定)なので、公差 $4$ の等差数列。

② 一般項を書く。 初項 $5$、公差 $4$。

$$a_n=5+(n-1)\times 4=4n+1$$

まとめ:漸化式が「差 = 一定」の形なら等差数列と即断できる。公差はその一定値。型さえ見抜けば公式に入れるだけだ。

発展。 「差をとる」という操作は、数列の次数を $1$ 下げる。

実験してみよう。 数列 $a_n=4n+1$($1$ 次式)の差をとる。

$$5,9,13,17,21\stackrel{\text{差}}{\to }4,4,4,4(\text{定数})$$

$1$ 回の差で、定数になった。

では、$2$ 次式ならどうか。 $a_n=n^2$ で試す。

$$1,4,9,16,25,36\stackrel{\text{差}}{\to }3,5,7,9,11\stackrel{\text{差}}{\to }2,2,2,2$$

$2$ 回の差で、定数。$3$ 次式 $a_n=n^3$ なら

$$1,8,27,64,125\to 7,19,37,61\to 12,18,24\to 6,6$$

$3$ 回の差で、定数($=6$)。

規則が見えた。

$$\boxed{k\text{ 次式の数列は、}k\text{ 回の差で定数になる}}$$

これは実用的な道具になる。数表だけ与えられて「一般項を求めよ」と言われたとき、差を何回とれば定数になるかを調べれば、次数が分かる。

例。 $2,6,12,20,30,\dots$ の一般項は?

$$\stackrel{\text{差}}{\to }4,6,8,10\stackrel{\text{差}}{\to }2,2,2$$

$2$ 回で定数 → $2$ 次式。

$a_n=A{n}^2+Bn+C$ と置いて、$3$ 点を代入すれば決まる($a_n=n^2+n$ になる)。

この技法を階差法という。 ニュートンが補間公式として体系化したもので、数表から法則を見つける古典的な方法だ。

差をとると次数が下がり、和をとると次数が上がる。 微分と積分の関係と、まったく同じ構造である。数列の差と和は、離散版の微積分である。

別解

等差数列を「階差型の特別な場合」として解く。階差型の公式はこうだった。

$$a_{n+1}-a_n=f(n)⟹a_n=a_1+\sum _{k=1}^{n-1}f(k)(n\geqq 2)$$

この問題では $f(n)=4$ で、定数だ。

$$a_n=5+\sum _{k=1}^{n-1}4$$

$4$ を $n-1$ 個足すのだから

$$\sum _{k=1}^{n-1}4=4(n-1)$$

$$a_n=5+4(n-1)=4n+1$$

公式と同じ答え

ここで気づいてほしい。

$$a_n=\underset{a_1}{\underbrace{5}}+\underset{d\times (n-1)}{\underbrace{4(n-1)}}$$

これは、等差数列の一般項の公式そのものだ。

$$a_n=a_1+(n-1)d$$

つまり、等差数列の公式は階差型の公式で $f(n)=$ 定数とした場合にほかならない。

なぜ差を足し上げると元に戻るのか。 実際に並べてみよう。

$$(a_2-a_1)+(a_3-a_2)+(a_4-a_3)+\cdots +(a_n-a_{n-1})$$

隣どうしが打ち消し合う。 $-a_2$ と $+a_2$、$-a_3$ と $+a_3$ $\dots$

$$=a_n-a_1$$

残るのは両端だけ。 望遠鏡を畳むように、途中がすべて消える。

$$a_n=a_1+(\text{差の総和})$$

これが階差型の公式の成り立ちである。

この視点の価値。 等差・等比・階差を、バラバラの公式として覚える必要がなくなる。

「差が一定 → 等差」も「差が $n$ の式 → 階差型」も、$1$ つの原理($=$ 差を足し上げれば元に戻る)の現れだと分かる。公式が $3$ つあるのではなく、原理が $1$ つあるだけだ。

方針

解答

⓪ 発想(どう考え始めるか) $\frac{a_{n+1}}{a_n}=3$ なので、比がいつでも $3$ で一定だ。

「比が一定」なら、等比数列である。

$$2\stackrel{\times 3}{\to }6\stackrel{\times 3}{\to }18\stackrel{\times 3}{\to }54$$

分母を払えば、見慣れた形に戻る。

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

差の形が等差だったように、比の形は等比だ。

• $a_{n+1}-a_n=d$(差が一定)→ 等差
• $\frac{a_{n+1}}{a_n}=r$(比が一定)→ 等比

引き算か、割り算か。 ここを読み取れば、型は決まる。まず分母を払って、いつもの形に直そう。

① 型を見抜く。 $\frac{a_{n+1}}{a_n}=3$(比が一定)なので、公比 $3$ の等比数列。

② 一般項を書く。 初項 $2$、公比 $3$。

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

まとめ:漸化式が「比 = 一定」の形なら等比数列。公比はその値。等差の「差」に対して、等比は「比」を見る、と対にして覚える。

発展。 「比が一定かどうか」を見る目は、現実のデータを読むときに役に立つ。

感染症の広がりを考えよう。$1$ 人の感染者が平均して $R$ 人にうつすとする($R$ を実効再生産数という)。世代ごとの感染者数は

$$a_{n+1}=R\cdot a_n$$

これは、この問題の漸化式と同じ形だ。

$R=3$ なら、$1$ 人から始まって

$$1,3,9,27,81,243,\dots$$

$5$ 世代で $243$ 倍。 これが「指数関数的増加」の速さである。では、$R$ を $1$ 未満にできたら?

$$R=0.9⟹1,0.9,0.81,0.729,\dots$$

減っていく。 やがて $0$ に近づく(収束する)。

$$\boxed{R>1\text{ なら爆発、}R<1\text{ なら収束}}$$

$R=1$ が分かれ目になる。 $R$ が $1.1$ か $0.9$ かで、結果は正反対になる。この $1$ という境目こそが、対策の目標になる。

同じ構造があちこちにある。

• 人口: $1$ 組の夫婦から生まれる子が平均 $2$ 人未満なら、人口は減る
• 核分裂: $1$ 個の中性子が次に $1$ 個以上を生むかどうかが、臨界の条件
• 投資: 年利 $r$ なら $a_{n+1}=(1+r)a_n$。複利は等比数列である

「比を見る」ことの意味。

差(増えた人数)を見ると「先週より $100$ 人増えた」で終わる。比を見ると「$1.2$ 倍になった」と分かり、来週の予測ができる。

等比数列の見方を持っている人は、変化のスピードそのものを読める。

$$\frac{a_{n+1}}{a_n}—\text{この 1 つの数が、未来を語る。}$$

別解

「比の積」でまとめて求める。比が与えられているのだから、比をそのまま掛け合わせてみよう。

$$\frac{a_2}{a_1}\times \frac{a_3}{a_2}\times \frac{a_4}{a_3}\times \cdots \times \frac{a_n}{a_{n-1}}$$

分子と分母が、次々に約分される。

$$=\frac{a_n}{a_1}$$

残るのは両端だけ。 望遠鏡を畳むように、途中がすべて消える(等差のときは差の「和」で消えた。等比では比の「積」で消える)。

一方、各因子はすべて $3$ である。 因子は $n-1$ 個。

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

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

公式と同じ答え。

さらに、この式を別の形に書き直してみる。

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

$3^n$ の形になった。

この形から分かること。 $a_n$ は指数関数 $y=\frac{2}{3}\cdot 3^x$ の、$x=1,2,3,\dots$ での値である。等差数列が $1$ 次関数($=$ 直線)の飛び飛びの値だったのと、ちょうど対をなす。

• 等差数列 $\leftrightarrow$ $1$ 次関数(まっすぐ増える)
• 等比数列 $\leftrightarrow$ 指数関数(加速して増える)

どちらの表示を使うか。

$$2\cdot 3^{n-1}\text{と}\frac{2}{3}\cdot 3^n$$

値はまったく同じ。 前者は「初項 $\times$ 公比の累乗」という数列としての見方、後者は「指数関数」という関数としての見方である。

確かめる。 $n=1$ で $\frac{2}{3}\times 3=2$、$n=4$ で $\frac{2}{3}\times 81=54$

$1$ つの数列に、$2$ つの見方がある。 場面に応じて、見やすいほうを使えばよい。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=3a_n-4$ は、掛けて、引く形だ。 前に見た $2a_n+1$ と同じ仲間だ。

形は $a_{n+1}=p{a}_n+q$。 $p=3$、$q=-4$。符号が変わっても、手順はまったく同じである。

特性方程式 $\alpha =3\alpha -4$ を解く。 $\alpha =2$。すると

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

$a_n-2$ が公比 $3$ の等比数列になる。

この $2$ という数の意味を、確かめておこう。 もし $a_1=2$ だったら、$3\times 2-4=2$ となり、ずっと $2$ のまま動かない。

$\alpha$ は「動かない値」である。 そこからのズレだけを追えばよい。それが特性方程式型の見通しである。

① 特性方程式を解く。 $\alpha =3\alpha -4$ より $2\alpha =4$、$\alpha =2$。

② $\alpha$ を引いて等比の形に。

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

③ 置きかえて等比数列に。 $b_n=a_n-2$ とおくと $b_{n+1}=3b_n$。初項 $b_1=a_1-2=1$。

$$b_n=1\cdot 3^{n-1}=3^{n-1}$$

④ $a_n$ に戻す。 $a_n=b_n+2$。

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

まとめ:引き算($-4$)でも手順は同じ。特性方程式で不動点 $\alpha =2$ を出し、そこからのズレ $a_n-2$ を等比数列とみる。$\alpha$ が答えの「定数部分」になる。

発展。 不動点には「安定」と「不安定」の $2$ 種類がある。

この問題の不動点は $2$、そしてズレは $3$ 倍ずつ拡大した。

$$d_{n+1}=3d_n$$

もし初項がぴったり $2$ なら、永遠に $2$ のまま。 だが、ほんのわずかでもズレると、たちまち吹き飛ぶ。

$$a_1=2.001⟹\text{ズレ }0.001\times 3^{n-1}⟹20\text{ 歩で }1000\text{ 以上}$$

これを不安定な不動点という。

イメージは鉛筆を立てること。 完全に垂直なら立ち続ける。だが $1$ 度でも傾けば、傾きはどんどん大きくなって倒れる。

逆に、係数の絶対値が $1$ より小さいと?

$$a_{n+1}=\frac{1}{2}{a}_n+1(\text{不動点 }\alpha =2)$$

ズレは半分ずつになる。 どこから始めても、$2$ に吸い寄せられる。これが安定な不動点だ(次の問題で扱う)。

すり鉢の底に置いたビー玉。 どこに置いても、転がって底に落ち着く。

$$\boxed{|p|>1\text{ なら発散(不安定)},|p|<1\text{ なら収束(安定)}}$$

この $1$ 行は力学系(時間とともに変化する系)の基礎になる。

現実の例。

• 経済: 金利や物価が均衡点に戻るか、暴走するか
• 生態系: 個体数が安定するか、絶滅・急増するか
• 気象: わずかな初期のズレが拡大する(バタフライ効果)

天気予報が $1$ 週間先までしか当たらないのも、これが理由だ。 大気の運動は不安定な系で、観測のわずかな誤差が指数関数的に拡大する。

$a_{n+1}=3a_n-4$。 この $1$ 行の中に、「予測できる系」と「予測できない系」を分ける境界がある。

別解

「$2$ からのズレ」だけを追いかける。特性方程式を「公式」としてでなく、考え方の流れとして見る別解である。

① 動かない値を探す。

「もし、ある値 $\alpha$ から始めたら、次もその $\alpha$ のまま」になる、そんな都合のいい値はあるか。

$$\alpha =3\alpha -4⟹\alpha =2$$

確かめる。 $a_n=2$ なら $a_{n+1}=3\times 2-4=2$。本当に動かない。

この $2$ を、不動点(動かない点)と呼ぶ。

② ズレを測る。

実際の初項は $a_1=3$。不動点 $2$ より、$1$ だけ上にいる。

$$d_n=a_n-2(\text{2 からのズレ})$$

$$d_1=3-2=1$$

③ ズレがどう変化するかを見る。

$$d_{n+1}=a_{n+1}-2=(3a_n-4)-2=3a_n-6=3(a_n-2)=3d_n$$

$$d_{n+1}=3d_n$$

ズレは毎回きっかり $3$ 倍になる。

$$d_n=1\cdot 3^{n-1}=3^{n-1}$$

④ ズレを、不動点に足し戻す。

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

本解と同じ答え

数列で確かめよう。

$$3,5,11,29,83,\dots$$

$$\text{ズレ:}1,3,9,27,81,\dots (\text{3 の累乗!})$$

きれいに $3$ 倍ずつ離れていく。この見方から分かること。数直線の上に $2$ を打つ。$a_1=3$ はそのすぐ右にいる。そして進むたびに、$2$ から $3$ 倍の速さで右へ吹き飛んでいく。

$a_n$ が複雑に見えたのは、「$2$」という基準がズレていたからだ。 基準を $2$ に取り直せば、ただの等比数列だった。特性方程式がしていることは、「原点をずらす」ことである。座標の原点を $2$ に移せば、数列は等比数列に見える。

方針

解答

⓪ 発想(どう考え始めるか) 証明すべきは「すべての自然数 $n$ で成り立つ」こと。

自然数は無限にある。 $1$ つずつ確かめていては、永久に終わらない。そこで、$2$ 段構えの仕掛けを使う。

• (I) $n=1$ で成り立つことを、実際に確かめる
• (II) 「$n=k$ で成り立つ」を仮定して、「$n=k+1$ でも成り立つ」を導く

この $2$ つで、なぜ無限個が片づくのか。ドミノ倒しを思い浮かべよう。(I) は「$1$ 枚目を倒す」こと。(II) は「$k$ 枚目が倒れれば $k+1$ 枚目も倒れる」という仕組みを作ること。

仕組みができていれば、$1$ 枚目を倒すだけで、あとは勝手に全部倒れる。

$$1\to 2\to 3\to 4\to \cdots$$

「$2$ 段で、無限個を証明する。」 この論法の枠組みそのものを、まず掴んでほしい。

(I) $n=1$ のとき。 左辺 $=1$、右辺 $=\frac{1\cdot 2}{2}=1$。成り立つ。

(II) $n=k$ を仮定する。 $1+2+\cdots +k=\frac{k(k+1)}{2}$ が成り立つとする。この両辺に、次の項 $k+1$ を足す。

$$1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)$$

右辺を $(k+1)$ でくくって整理する。

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

これは、もとの式で $n=k+1$ とした右辺 $\frac{(k+1)\{(k+1)+1\}}{2}$ に一致する。よって $n=k+1$ でも成り立つ。

結論。 (I)(II) より、すべての自然数 $n$ で成り立つ。

まとめ:数学的帰納法は「ドミノ倒し」。(I) 最初の $1$ 枚を倒し、(II) $k$ 枚目が倒れれば $k+1$ 枚目も倒れる、を示す。この $2$ つで全部倒れる(全部で成立)。仮定した式を使うところがヤマだ。

発展。 「たくさん確かめたから正しい」という推論は、数学では通らない。

その理由がよく分かる例がある。

オイラーの式。

$$f(n)=n^2+n+41$$

$n=0$ から順に、値を出してみよう。

$$41,43,47,53,61,71,83,97,113,131,\dots$$

すべて素数だ。

$n=20$ でも $461$($=$ 素数)。$n=30$ でも $971$($=$ 素数)。$n=39$ でも $1601$($=$ 素数)。

$n=0$ から $n=39$ まで、$40$ 個すべてが素数になる。「これは、すべての $n$ で素数だ」と言いたくなる。だが、$n=40$ で

$$40^2+40+41=1681=41\times 41$$

素数ではない。

$40$ 個の成功のあとに、あっさり反例が現れた。これが「実験は証明ではない」ということだ。

もっと極端な例もある。 ある予想は $10^{40}$ 以下のすべての数で成り立つのに、それより大きいところで破れることが証明されている(スキューズ数の話)。計算で確かめられる範囲では、反例は見つからない。

だからこそ、帰納法が要る。帰納法の (II) は「$k$ で成り立てば $k+1$ でも成り立つ」という仕組みを証明する。仕組みさえ作れば、確かめていない先の無限個まで、まとめて保証できる。

$$\text{有限の確認}\ne \text{無限の証明}$$

「$1$ 万回試して大丈夫だった」は、数学では何も言っていないのと同じ。逆に、$2$ 行の帰納法は無限個を完全に押さえる。

これが、数学が「証明」にこだわる理由である。 実験で予想は立てられるが、すべての自然数で成り立つことを保証できるのは、証明だけである。

別解

帰納法の (II) は、実は「階差の確認」にすぎない。この見方を知ると、帰納法の計算がずっと軽くなる。証明したい式の右辺を、関数と見る。

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

主張は「左辺の和 $=$ $f(n)$」だ。(II) で何をしているか、よく見てほしい。$n=k$ で正しいと仮定すると、左辺の和は $f(k)$。そこに新しい項 $k+1$ を足したものが、$f(k+1)$ になってほしい。

$$f(k)+(k+1)\stackrel{?}{=}f(k+1)$$

移項すれば、確かめるべきことはこれだけだ。

$$\boxed{f(k+1)-f(k)=k+1}$$

「右辺の階差が、足す項に一致するか」が、(II) の中身のすべてである。

実際に計算する。

$$f(k+1)-f(k)=\frac{(k+1)(k+2)}{2}-\frac{k(k+1)}{2}$$

共通因数 $\frac{k+1}{2}$ でくくる。

$$=\frac{k+1}{2}\{(k+2)-k\}=\frac{k+1}{2}\times 2=k+1$$

足す項 $k+1$ に、ぴったり一致した。あとは (I) の $f(1)=1$ を確かめれば終わり。

この見方の強み。

• やることが $1$ 行に決まる。 「$f(k+1)-f(k)$ を計算して、足す項と比べる」だけ
• 式が複雑でも迷わない。 $\Sigma k^2=\frac{n(n+1)(2n+1)}{6}$ でも、やることは同じ($f$ の階差が $(k+1{)}^2$ になるか)
• なぜ帰納法が使えるのかが見える。 「初項が合っていて、階差も合っている $\Rightarrow$ 全部合っている」というのは、階差型の漸化式そのものだ

そして、大事な但し書き。

帰納法は「確認」の道具であって、「発見」の道具ではない。 $\frac{n(n+1)}{2}$ という式は、帰納法からは出てこない。

式は実験や工夫(逆順に足す、図で数える)から予想する。 帰納法はその予想を確定させる最後の一手である。

予想する道具と、確定させる道具。 $2$ つを両手に持って初めて、数学は進む。