等比型の漸化式

方針

解答

⓪ 発想 — どう考え始めるか。 前問は「足す」型だった。今度は $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$ 回。