SICP: Exercise 1.13
\( \mathrm{Fib}(n) \) が \( \frac{\phi^n}{\sqrt{5}} \; \left( \phi = \frac{1 + \sqrt{5}}{2} \right) \) に最も近い整数であることの証明。
まずはヒントから
\( \psi = \frac{1 - \sqrt{5}}{2} \) とおき
$$ \mathrm{Fib}(n) = \frac{\phi^n - \psi^n}{\sqrt{5}} $$
を証明する。
$$ \mathrm{Fib}(n) = \begin{cases} 0 & \text{if \(n = 0\)} \\ 1 & \text{if \(n = 1\)} \\ \mathrm{Fib}(n - 1) + \mathrm{Fib}(n - 2) & \text{otherwise} \end{cases} $$
\( \mathrm{Fib}(n) = f_n \) とおくと、\( n \geq 2 \) で
$$ f_n = f_{n - 1} + f_{n - 2} \\ f_n - f_{n - 1} - f_{n - 2} = 0 $$
\( f_n - \alpha f_{n - 1} = \beta (f_{n - 1} - \alpha f_{n - 2}) \) とおくと、
$$ f_n + (\alpha + \beta)f_{n - 1} + \alpha \beta f_{n - 2} = 0 $$
係数比較より \( \alpha + \beta = -1,\ \alpha\beta = -1 \)。従って、\( \alpha \) と \( \beta \) は 2 次方程式 \( x^2 - x - 1 = 0 \) の解である。
これを解くと \( x = \frac{1 \pm \sqrt{5}}{2} \)。解の大きい方を \( \phi \)、小さい方を \( \psi \) とする。
\( \alpha \), \( \beta \) に \( x \) の 2 通りの場合を代入すると
$$ \begin{cases} f_n - \phi f_{n - 1} = \psi(f_{n - 1} - \phi f_{n - 2}) \\ f_n - \psi f_{n - 1} = \phi(f_{n - 1} - \psi f_{n - 2}) \end{cases} $$
これより
$$ \begin{align*} f_n - \phi f_{n - 1} &= \psi^{n - 1}(f_1 - \phi f_0) = \psi^{n - 1} \tag{1} \\ f_n - \psi f_{n - 1} &= \phi^{n - 1}(f_1 - \psi f_0) = \phi^{n - 1} \tag{2} \end{align*} $$
\( (2) - (1) \) より
$$ (\phi - \psi) f_{n - 1} = \phi^{n - 1} - \psi^{n - 1} \\ (\phi - \psi) f_n = \phi^n - \psi^n $$
したがって
$$ f_n = \frac{\phi^n - \psi^n}{\phi - \psi} = \frac{\phi^n - \psi^n}{\sqrt{5}} $$
最も近い整数
「整数 \( n \) が実数 \( a \) に最も近い整数である」とは
$$ |a - n| \leq \frac{1}{2} $$
と同値である。これは後に補題として示す。
\( f_n \) が \( \frac{\phi^n}{\sqrt{5}} \) に最も近い整数であること、すなわち
$$ \left| \frac{\phi^n}{\sqrt{5}} - f_n \right| \leq \frac{1}{2} $$
を示す。式を変形していくと
$$ \left| \frac{\psi^n}{\sqrt{5}} \right| \leq \frac{1}{2} \\ \left| \psi^n \right| \leq \frac{\sqrt{5}}{2} \\ \left| \left( \frac{1 - \sqrt{5}}{2} \right)^n \right| \leq \frac{\sqrt{5}}{2} $$
を示せばよい。
まず
$$ -1 = \frac{-2}{2} = \frac{1 - \sqrt{9}}{2} < \frac{1 - \sqrt{5}}{2} < \frac{1 - \sqrt{1}}{2} = 0 $$
より
$$ -1 < \frac{1 - \sqrt{5}}{2} < 0 \\ 0 < \left| \frac{1 - \sqrt{5}}{2} \right| < 1 \\ 0 < \left| \left( \frac{1 - \sqrt{5}}{2} \right)^n \right| < 1 $$
である。また
$$ 1 = \frac{2}{2} = \frac{\sqrt{4}}{2} < \frac{\sqrt{5}}{2} $$
であるから
$$ \left| \left( \frac{1 - \sqrt{5}}{2} \right)^n \right| \leq \frac{\sqrt{5}}{2} $$
が成り立つ。したがって、\( f_n \) は \( \frac{\phi^n}{\sqrt{5}} \) に最も近い整数である。
補題：最も近い整数
整数 \( n \) が実数 \( a \) に最も近い整数である \( \Leftrightarrow |a - n| \leq \frac{1}{2} \) を示す。
必要性
\( n \) を \( a \) に最も近い整数とすると
- \( n \leq a \leq n + 1 \)
- \( n - 1 \leq a \leq n \)
のいずれかの場合が考えられる。
1. の場合、\( |a - n| + |a - (n + 1)| = 1 \)。\( |a - n| \leq |a - (n + 1)| \) であるから
$$ |a - n| + |a - n| = 2|a - n| \leq 1 \quad \therefore |a - n| \leq \frac{1}{2} $$
2. の場合、\( |a - (n - 1)| + |a - n| = 1 \)。\( |a - n| \leq |a - (n - 1)| \) であるから
$$ |a - n| + |a - n| = 2|a - n| \leq 1 \quad \therefore |a - n| \leq \frac{1}{2} $$
以上から必要性が示された。
十分性
\( |a - n| = \frac{1}{2} \) の場合、\( a = n \pm \frac{1}{2} \)、すなわち \( a \) は半整数であるから自明。\( |a - n| < \frac{1}{2} \) の場合、開区間 \( \left( a - \frac{1}{2}, a + \frac{1}{2} \right) \) に含まれる整数は、\( \left( a + \frac{1}{2} \right) - \left( a - \frac{1}{2} \right) = 1 \) より \( n \) のみ。よって、\( n \) は \( a \) に最も近い整数である。
以上からこの補題が示された。
参考文献
- Ken Dyck, Solution to SICP Exercise 1.13
- 補題は同級生 ZON ☆ くんの助言
