COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

線形漸化式

$2$ 項間線形漸化式

問題≪ハノイの塔≫

 地面に $3$ 本の棒が立てられており, そのうちの $1$ 本に穴の開いた半径の異なる円盤が半径の大きい順に通されている. $1$ 本の棒の最も上にある $1$ 枚を別の棒の最も上に移す操作を $1$ 手と数え, $1$ 本の棒の最も上にある $n$ 枚を別の棒の最も上に移すための手数の最小値を $a_n$ とおく. ただし, いずれの段階においても小さい円盤の上に大きい円盤は置かないとする.
(1)
すべての正の整数 $n$ に対して $a_{n+1} = 2a_n+1$ が成り立つことを説明せよ.
(2)
数列 $\{ a_n\}$ の一般項を求めよ.

解答例

(1)
最初に円盤を通された棒を A とし, 残りの棒を B, C とする. 棒 A の最も上にある $n+1$ 枚を棒 B の最も上に移すためには, まず上の $n$ 枚を棒 C に移し, 次に棒 A に残された $1$ 枚を棒 B に移し, 最後に棒 C に移された $n$ 枚を棒 B に移す必要がある.
ゆえに, \[ a_{n+1} = a_n+1+a_n = 2a_n+1 \quad \cdots [1]\] が成り立つ.
(2)
\[ \alpha = 2\alpha +1 \cdots [2]\] を解くと, $\alpha = -1$ となる. $[1]-[2]$ から \[ a_{n+1}-\alpha = 2(a_n-\alpha )\] となるので, $\alpha = -1$ を代入すると \[ a_{n+1}+1 = 2(a_n+1)\] となる. よって, $\{ a_n+1\}$ は初項 $a_1+1 = 1+1 = 2,$ 公比 $2$ の等比数列であるから, \[ a_n+1 = 2^n\] つまり \[ a_n = 2^n-1\] である.

背景

 本問は, フランスの数学者リュカによって考案された「ハノイの塔」(tower of Hanoi)と呼ばれるパズルの手数の最小値を求める問題である. $n+1$ 枚の場合に全体を $n$ 枚のかたまりと $1$ 枚に分けて考えると $n$ 枚の場合が現れ, $a_n,$ $a_{n+1}$ の関係式が得られた. この方法は, 漸化式を立てて場合の数を求める問題の定石の $1$ つと言える.

$3$ 項間線形漸化式

問題≪フィボナッチ数列の一般項≫

 $1$ 歩目は $1$ 段だけ上るとし, $2$ 歩目以降は $1$ 歩で $1$ 段上ることも $2$ 段上ることもできるとして, $n$ 段の階段を上る方法の総数を $F_n$ とおく.
(1)
$F_{n+2} = F_n+F_{n+1}$ が成り立つことを示せ.
(2)
数列 $\{ F_{n+1}-\alpha F_n\},$ $\{ F_{n+1}-\beta F_n\}$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列となるような定数 $\alpha,$ $\beta\ (\alpha < \beta )$ を $1$ 組求めよ.
(3)
数列 $\{ F_n\}$ の一般項を求めよ.

解答例

(1)
$n+2$ 段の階段を上るとき, 最後の $1$ 歩に着目すると, 次の $2$ つの場合が考えられる.
(i)
最後の $1$ 歩で $2$ 段上る場合. $n+2$ 段を上る方法は, $n$ 段の上り方 $F_n$ 通りだけある.
(ii)
最後の $1$ 歩で $1$ 段上る場合. $n+2$ 段を上る方法は, $n+1$ 段の上り方 $F_{n+1}$ 通りだけある.
(i), (ii) は排反であるから, \[ F_{n+2} = F_n+F_{n+1} \quad \cdots [1]\] が成り立つ.
(2)
数列 $\{ F_{n+1}-\alpha F_n\},$ $\{ F_{n+1}-\beta F_n\}$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列であるとき, \begin{align*} F_{n+2}-\alpha F_{n+1} &= \beta (F_{n+1}-\alpha F_n), \\ F_{n+2}-\beta F_{n+1} &= \alpha (F_{n+1}-\beta F_n) \end{align*} から \[ F_{n+2} = (\alpha +\beta )F_{n+1}-\alpha\beta F_n \quad \cdots [2]\] が成り立つ. $[1],$ $[2]$ から, \[\alpha +\beta = 1,\quad \alpha\beta = -1\] が成り立てばよい. このとき, $\alpha,$ $\beta$ は $2$ 次方程式 $x^2-x-1 = 0$ の解であるから, 条件を満たす $\alpha,$ $\beta$ の組として \[ (\alpha,\beta ) = \left(\frac{1-\sqrt 5}{2},\frac{1+\sqrt 5}{2}\right)\] がとれる.
(3)
明らかに $F_1 = 1$ であり, $1$ 歩目は $1$ 段だけ上るという条件から $F_2 = 1$ である. よって, 数列 $\{ F_{n+1}-\alpha F_n\},$ $\{ F_{n+1}-\beta F_n\}$ の初項は, それぞれ \begin{align*} F_2-\alpha F_1 = 1-\alpha &= \frac{1+\sqrt 5}{2} = \beta, \\ F_2-\beta F_1 = 1-\beta &= \frac{1-\sqrt 5}{2} = \alpha \end{align*} である. したがって, $\alpha,$ $\beta$ の取り方から, \begin{align*} F_{n+1}-\alpha F_n &= \beta ^n, \\ F_{n+1}-\beta F_n &= \alpha ^n \end{align*} が成り立つ. 辺々を引くと \[ (\beta -\alpha )F_n = \beta ^n-\alpha ^n\] となるので, $\beta -\alpha = \sqrt 5$ から \[ F_n = \frac{1}{\sqrt 5}\left\{\left(\frac{1+\sqrt 5}{2}\right) ^n-\left(\frac{1-\sqrt 5}{2}\right) ^n\right\}\] が成り立つ.

背景

  • 初期条件 $F_1 = F_2 = 1$ と隣接 $3$ 項間漸化式 $F_{n+2} = F_n+F_{n+1}$ で定まる数列 \[\{ F_n\}:1,1,2,3,5,8,13,21,34,55,89,144,\cdots\] を「フィボナッチ数列」と呼ぶ. この数列の項は「フィボナッチ数」と呼ばれ, 花びらの枚数, 植物の種が並んでできるらせんの本数など, 自然界でよく見られる整数である.「フィボナッチ数列」は, 次の問題でも登場する: 先頭は動かないように, $2$ 番目以降は動かないか隣に移るように, $1$ 列に並んだ $n$ 人を並び替える方法の総数は $F_n$ である.
  • $\left|\dfrac{\alpha}{\beta}\right| = \dfrac{\sqrt 5-1}{1+\sqrt 5} < 1$ から \begin{align*} \frac{F_{n+1}}{F_n} &= \frac{\beta ^{n+1}-\alpha ^{n+1}}{\beta ^n-\alpha ^n} = \frac{\beta -\alpha\left(\dfrac{\alpha}{\beta}\right) ^n}{1-\left(\dfrac{\alpha}{\beta}\right) ^n} \\ &\to \beta = \frac{1+\sqrt 5}{2} \quad (n \to \infty ) \end{align*} であることもよく知られている(数学 III).