黄金比(黄金率)


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.
証明終わり