数学B / 漸化式と数学的帰納法

特性方程式型(基本)

★ 基礎漸化式特性方程式

問題

$a_{1} = 1$ 、 $a_{n + 1} = 2 a_{n} + 1$ で定まる数列 ${a_{n}}$ の一般項を求めよ。

ヒントを見る

『 $2$ 倍して定数を足す』型には、両辺から同じ数を引いて『何かの等比数列』に変形する方法がある。その『同じ数』の見つけ方を思い出そう。

解答・解説

方針

$a_{n + 1} = p a_{n} + q$ の型。特性方程式 $α = 2 α + 1$ を解いて $α = - 1$ 。両辺から $α$ を引くと $a_{n + 1} - α = 2 (a_{n} - α)$ となり、 ${a_{n} - α}$ が等比数列になる。

解答

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

等差でも等比でもない。だが、書き出すと正体が見える。

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

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

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

きれいな $2$ の累乗になった!

つまり $a_{n} + 1$ は等比数列である。 $1$ だけずらすと、等比に化けるわけだ。

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

「ズレを吸収して等比にする」 — これが特性方程式型の核心である。

重要

a_{n + 1} = p a_{n} + q

は、特性方程式

α = p α + q

の解

α

で

a_{n + 1} - α = p (a_{n} - α)

と変形する

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

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

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

③ 置きかえて等比数列にする。 $b_{n} = a_{n} + 1$ とおくと $b_{n + 1} = 2 b_{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 \neq = 1$ )は「特性方程式で $α$ を出す → $a_{n} - α$ を等比数列とみる」。 $α$ は「動かない値(不動点)」で、そこからのズレが等比的に変化する、というイメージだ。

発展 — 一歩先へ。 $a_{n} = 2^{n} - 1$ という数列は、パズルの世界で有名だ。

ハノイの塔。

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

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

最小の手数は何回か。

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

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

$h_{n} = 2 h_{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 1 0^{19}$

$1$ 秒に $1$ 手動かしても、約 $5850$ 億年かかる。 宇宙の年齢( $138$ 億年)の $40$ 倍以上だ。世界の終わりは、当分こない。

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

$a_{n + 1} = 2 a_{n} + 1$ 。 この短いルールが、パズルの手数と、人類が知る最大の素数の両方を生んでいる。

答

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

別解

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

邪魔なのは、末尾の $+ 1$ だ。 この定数さえ消えれば、話は簡単になる。

定数を消す常套手段が「引き算」である。

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

$a_{n + 2} = 2 a_{n + 1} + 1$ $a_{n + 1} = 2 a_{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} = 2 b_{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 ≧ 2$ で

$a_{n} = a_{1} + k = 1 \sum n - 1 b_{k} = 1 + k = 1 \sum n - 1 2^{k}$

等比数列の和。

$k = 1 \sum 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$ つの道を比べてみる。

本解(特性方程式): ズレの基準点 $α$ を見つけ、 $a_{n} - α$ を等比にする
別解(階差): $2$ 式を引いて定数を消し、差 $b_{n}$ を等比にする

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

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

ポイント

特性方程式 $α = p α + q$ で $α$ を求める。
$a_{n} - α$ が公比 $p$ の等比数列になる。

よくある間違い

特性方程式を $α = 2 α$ と書いてしまい、定数項 $+ 1$ を落とす。特性方程式は「 $a_{n + 1}$ も $a_{n}$ も $α$ に置き換えた式」なので、定数はそのまま残る
$α = - 1$ を求めたあと、 $a_{n + 1} + 1 = 2 (a_{n} + 1)$ の初項を $a_{1} = 1$ のままにする。等比数列になるのは $a_{n} + 1$ なので、初項は $a_{1} + 1 = 2$
最後に $- 1$ を戻し忘れて $a_{n} = 2^{n}$ で終える。求めたのは $a_{n} + 1$ であって $a_{n}$ ではない