理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

問題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に対して単調減少なのはあきらか。ってことなので、言葉足らずな感じだけど証明できたんじゃないかなとか思ったりしている。