피보나치 수 에필로그

어제 피보나치 수에 대한 포스팅을 하고 나서 옛날 생각이 좀 났다. SICP스터디 모임(TSG의 전신)에서 몇 년간 책을 계속 읽고 연습문제를 풀었는데, 피보나치 수에 대한 것도 상당수 그 때 책에서 보고 “오오~ 이런 세계가!”라며 감탄했던 내용이다. 피보나치 수와 소수 찾는 법, 뉴턴메소드가 모두 1장 앞쪽에 몰려 나와 사람들을 괴롭히지만, 그곳만 넘어가면 매우 즐거운 책이다. 본래 코딩을 취미로 삼은지는 25년정도 되었지만, 취미가 덕질로 업글된건 SICP를 보면서부터다.

옛날에 도쿠위키에 문제 풀면서 정리한다고 고생했던게 생각난다. 지금 ipython notebook을 블로깅 플랫폼으로 쓰고 있는 상황에서 그때를 돌이켜보면 정말 삽질로 점철된 시간들이었지만 … 그래도 그렇게 열심히 했던걸 보면, 체력이 지금보다 훨씬 좋았구나 싶다.

간만에 생각난 김에 어제의 피보나치 포스팅의 에필로그로 피보나치 수 일반항 증명으로 마무리. 사실 이 외에도 피보나치 수만 가지고도 파고들 수 있는건 무궁무진하다. 하지만 여백이 부족한 관계로 여기까지만 하고 더 이상은 손대지 않겠다.

SICP 연습문제 1.13번이다. 링크는 여기 있다.


Ex 1.13: Prove that $Fib(n)$ is the closest integer to $\phi^{n}/\sqrt{5}$, where $\phi = (1+\sqrt{5})/2$.

Hint: Let $\psi=(1-\sqrt{5})/2$. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that $Fib(n)=(\phi^{n}-\psi^{n})/\sqrt{5}$


시킨대로 귀납법을 써 보겠습니다.

1. n=0, n=1 인 경우 $Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$ 가 성립한다.

  • $Fib(0)=(\phi^0-\psi^0)/\sqrt{5}=(1-1)/\sqrt{5}=0$
  • $Fib(1)=(\phi^1-\psi^1)/\sqrt{5}=(\phi-\psi)/\sqrt{5}=\frac{(1+\sqrt{5})-(1-\sqrt{5})}{2}/\sqrt{5}=\sqrt{5}/\sqrt{5}=1$

Fib(0)=0, Fib(1)=1 이다.

2. $n>=2$인 임의의 정수 $n$에 대해서 $Fib(n-1)$, $Fib(n-2)$가 위 식을 만족하면 $Fib(n)$도 위 식을 만족한다.

정의에 의해,

  • $Fib(n)=Fib(n-1)+Fib(n-2)$ 이다.

$Fib(n-1)$, $Fib(n-2)$가 위 식을 만족한다고 했으므로,

  • $Fib(n-1)=(\phi^{n-1}-\psi^{n-1})/\sqrt{5}$
  • $Fib(n-2)=(\phi^{n-2}-\psi^{n-2})/\sqrt{5}$

이 식을 넣으면,

  • $Fib(n)=(\phi^{n-1}-\psi^{n-1})/\sqrt{5} + (\phi^{n-2}-\psi^{n-2})/\sqrt{5}=[\phi^{n-2}(\phi+1)-\psi^{n-2}(\psi+1)]/\sqrt{5}$

가 된다. 그런데 $\psi$, $\phi$를 제곱해보면 아래같은 결과가 나온다.

  • $\phi^2=[(1+\sqrt{5})/2]^{2}=(1+2\sqrt{5}+5)/4=(3+\sqrt{5})/2=1+\phi$
  • $\psi^2=[(1-\sqrt{5})/2]^{2}=(1-2\sqrt{5}+5)/4=(3-\sqrt{5})/2=1+\psi$

따라서 $\phi+1$, $\psi+1$ 을 각각 $\phi^2$, $\psi^2$ 로 바꾸어 넣을 수 있다.

  • $Fib(n)=[\phi^{n-2}(\phi+1)-\psi^{n-2}(\psi+1)]/\sqrt{5}=[\phi^{n-2}\phi^{2}-\psi^{n-2}\psi^{2}]/\sqrt{5}=(\phi^n-\psi^n)/\sqrt{5}$

… !!! ??? 신기하게도 아래 식이 증명되었다 !!!

$$Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$$

3. $Fib(n)$ 은 정수다.

식을 다시 써보자.

$Fib(n)=\phi^n/\sqrt{5}-\psi^n/\sqrt{5}$

우리는 $\phi$, $\psi$ 값을 계산할 수 있다.

In [1]:
import math

phi = (1.0+math.sqrt(5.0))/2
psi = (1.0-math.sqrt(5.0))/2

print("ϕ=%.3f, ψ=%.3f" % (phi, psi))
print("sqrt(5.0)=%.3f" % math.sqrt(5.0))

for i in range(1, 10):
    print("%.3f" % ((psi**i)/math.sqrt(5.0)))
ϕ=1.618, ψ=-0.618
sqrt(5.0)=2.236
-0.276
0.171
-0.106
0.065
-0.040
0.025
-0.015
0.010
-0.006

보면 알겠지만, 1이상의 모든 정수 $n$에 대해서 $\psi^{n}/\sqrt{5}$의 절대값은 0.5보다 작다.

$Fib(n)$은 $\phi^{n}/\sqrt{5}$에서 절대값이 0.5보다 작은 수를 뺀 정수이므로, $Fib(n)$은 $\phi^{n}/\sqrt{5}$에 가장 가까운 정수 라고 할 수 있다.

해보자

위 일반항을 가지고 파이썬 함수를 만들어 보자.

In [29]:
import math
phi = (1.0+math.sqrt(5.0))/2.0

def fibo_iter(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a+b
    return a

def fibo(n):
    return int(phi**n/math.sqrt(5) + 0.5)

for i in range(0, 1000):
    a = fibo_iter(i)
    b = fibo(i)
    if a != b:
        print("fibo_iter != fibo at n=%d: %d vs %d" % (i, a, b))
        break
else:
    print("Looks good")
fibo_iter != fibo at n=71: 308061521170129 vs 308061521170130

아쉽게도 실수 계산인 만큼 정확도에 문제가 있어 보인다. :’(

아… 보람없다.

Comments