問題1-13 - 理系学生日記

$\phi$ を黄金比とおいて、フィボナッチ数F(n)が $\phi^n/\sqrt 5$ にもっとも近い整数であることを証明するよ！

まずヒントどおり、 $\psi=(1-\sqrt 5)/2$ として、 $F(n)=\frac{\phi^n-\psi^n}{2}$ を数学的帰納法で証明。
(1) n=0のとき、 $\text{Fib}(0)=0=\frac{\phi^0-\psi^0}{2}$
(2) n=1のとき、 $\text{Fib}(1)=1=\frac{\phi^1-\psi^1}{2}$
(3) n=k+2のとき
　 $F(k+1)=\frac{\phi^{k+1}-\psi^{k+1}}{\sqrt 5}$ と $F(k)=\frac{\phi^{k}-\psi^{k}}{\sqrt 5}$ が成立すると仮定します。
そしたら、
　 $\text{Fib}(k+2)=$
　 $=\text{Fib}(k+1)+\text{Fib}(k)$ （∵Fibの定義より）
　 $=\frac{\phi^{k+1}-\psi^{k+1}}{\sqrt 5}+\frac{\phi^{k}-\psi^{k}}{\sqrt 5}$ 　（∵仮定より）
　 $=\frac{\phi^{k-1}(\phi+1)-\psi^{k-1}(\psi+1)}{\sqrt 5}$
　 $=\frac{\phi^{k+1}-\psi^{k+1}}{\sqrt 5}$ （∵ $\phi^2=\phi+1$ ， $\psi^2=\psi+1$ より）

(1),(2),(3)より成立するかんじです。

そしたら今度、 $F(n)=\frac{\phi^n}{\sqrt 5}-\text{Fib}(n)$ を考えると、
$F(n)=\frac{\psi^n}{\sqrt 5}$
このとき、 $F(0)=\frac{1}{\sqrt 5}<\frac{1}{2}$ 。
で、 $|\psi|<1$ なので、F(n)がn>0に対して単調減少なのはあきらか。ってことなので、言葉足らずな感じだけど証明できたんじゃないかなとか思ったりしている。