Sussman(サスマン)の「計算機プログラムの構造と解釈」Structure and Interpretation of Computer Programの練習問題 1.13.
Rubyを片手に計算機として使いながら解きました。
qr5を5の平方根、fi = (1 + qr5)/2 (黄金比)とした場合、フィボナッチ関数Fib(n)が(fi**n)/qr5に最も近い整数であることを証明せよ。 (**はRubyの表記でfi**nはfiのn乗) ヒント:psi = (1 - qr5)/2 とし、帰納法を用いて、まず Fib(n) = (fi**n - psi**n)/qr5 を証明することにより命題を証明する。 # example: # p fib(30) #=> 832040 # (fi**n)/qr5 = ((1+qr5)/2)**30/qr5 = 832040.000000241 fi = (1 + qr5)/2 psi = (1 - qr5)/2 ヒントに従い、まず下記の補題(*)を証明する。 (*) Fib(n) = (fi**n - psi**n)/qr5 帰納法で証明するために最初にnが0の場合と1の場合を証明する。 Fib(0) = (fi**0 - psi**0)/qr5 = 0 Fib(1) = (fi**1 - psi**1)/qr5 fi - psi = qr5 => Fib(1) = qr5/qr5 = 1 次に帰納部分の証明に入る。 n-1とn-2にの場合に補題(*)が成立しているとしたときにnの場合にも成立することを証明する。 Fib(n) = Fib(n-1) + Fib(n-2) = (fi**(n-1) - psi**(n-1) + fi**(n-2) - psi**(n-2)) / qr5 = ((fi+1)*fi**(n-2) - (psi+1)*psi(n-2)) / qr5 ところで、fiは黄金比(1 + qr5)/2であり、下記が成立する。 fi**2 = fi+1 また、簡単な計算により、下記が成立することが確かめられる。 (2) psi**2 = psi+1 fi+1とpsi+1に代入する。 (fi**2*fi**(n-2) - psi**2*psi**(n-2)) / qr5 = (fi**n - psi**n) / qr5 以上でヒント部分の証明終わり。 さて psi = -0.618であることから、 (fi**n - psi**n) / qr5 nが2以上の場合、psi**nは1以下となり、 Fib(n)はほぼfi**n/qr5となる。 Q.E.D. 証明終わり