Scheme - 手続きによる抽象の構築(手続きとその生成するプロセス(木構造再帰(帰納法, Fibonacci数)))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著)ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著)Julie Sussman (原著)
Gerald Jay Sussman (原著)和田 英一 (翻訳)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.2(木構造再帰)、問題 1.13.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)
• Scheme手習い

問題 1.13.

$n=0$ のとき、
$\begin{array}{l}Fib(0)=0,\frac{{\varphi }^0-{\psi }^0}{\sqrt{5}}=0\\ Fib(0)=\frac{{\varphi }^0-{\psi }^0}{\sqrt{5}}\end{array}$

$n=1$のとき、
$\begin{array}{l}Fib(1)=1,\frac{{\varphi }^1-{\psi }^1}{\sqrt{5}}=\frac{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}{\sqrt{5}}=1\\ Fib(1)=\frac{{\varphi }^1-{\psi }^1}{\sqrt{5}}\end{array}$

$0\le n<k(k>1)$
を満たす、すべてのnについて、
$Fib(n)=\frac{{\varphi }^n-{\psi }^n}{\sqrt{5}}$
が成り立つと仮定する。

そのとき、
$\begin{array}{l}Fib(k)=Fib(k-1)+Fib(k-2)\\ =\frac{{\varphi }^{k-1}-{\psi }^{k-1}}{\sqrt{5}}+\frac{{\varphi }^{k-2}-{\psi }^{k-2}}{\sqrt{5}}\\ =\frac{{\varphi }^{k-2}(\varphi +1)-{\psi }^{k-2}(\psi +1)}{\sqrt{5}}\end{array}$
また、
$\begin{array}{l}{\varphi }^2=\frac{6+2\sqrt{5}}{4}=\frac{3+\sqrt{5}}{2}=\varphi +1\\ {\psi }^2=\frac{6-2\sqrt{5}}{4}=\frac{3-\sqrt{5}}{2}=\psi +1\end{array}$
よって、
$Fib(k)=\frac{{\varphi }^k-{\psi }^k}{\sqrt{5}}$

したがって、
$Fib(n)=\frac{{\varphi }^n-{\psi }^n}{\sqrt{5}}$
はすべての自然数について成り立つ。

このことから、
$\begin{array}{l}\left|Fib(n)-\frac{{\varphi }^n}{\sqrt{5}}\right|=\frac{\left|{\psi }^n\right|}{\sqrt{5}}\\ \left|\psi \right|=\frac{\sqrt{5}-1}{2}<1\\ \left|Fib(n)-\frac{{\varphi }^n}{\sqrt{5}}\right|\le \frac{1}{\sqrt{5}}<\frac{1}{2}\end{array}$
となり、 $Fib(n)$は$\frac{{\varphi }^n}{\sqrt{5}}$ に最も近い整数である。

証明終