読者です 読者をやめる 読者になる 読者になる

ochalog

Ruby と MediaWiki が好きな電子・情報系の学生のブログ。

SICP: Exercise 1.13

SICP 数学

\( \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 \) に最も近い整数とすると

  1. \( n \leq a \leq n + 1 \)
  2. \( 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 \) に最も近い整数である。

以上からこの補題が示された。

参考文献

  1. Ken Dyck, Solution to SICP Exercise 1.13
  2. 補題は同級生 ZON ☆ くんの助言