연습문제 1.13

PI = (1 + sqrt(5)) / 2
PSI = (1 - sqrt(5)) / 2

일때 우선 힌트를 증명해보자..

Fib(n) = (PI^n - PSI^n)/sqrt(5)

임을 증명하자.

먼저 수학적 귀납법으로 증명하기위해 초기조건이 위의 식을 만족함을 보여야한다.

Fib(0) = (PI^0 - PSI^0) / sqrt(5) = (1 - 1) / sqrt(5) = 0 / sqrt(5) = 0
Fib(1) = (PI^1 - PSI^1) / sqrt(5) = ( (1+ sqrt(5))/2 - ((1-sqrt(5))/2) ) / sqrt(5) = (sqrt(5)) / sqrt(5) = 1

따라서 위의 식은 초기조건을 만족한다.
이제 Fib(n-1)항과 Fib(n-2)항이 위의 조건을 만족한다고 가정하고 Fib(n)을 구해보자

정의에 따라 Fib(n) 은

Fib(n) = Fib(n-1) + Fib(n-2) = (PI^(n-1) - PSI^(n-1)) / sqrt(5) + (PI^(n-2) - PSI^(n-2)) / sqrt(5)
= ( (PI+1)*PI^(n-2) - (PSI+1)*PSI^(n-2) ) / sqrt(5)

이다..

PI는 황금비를 나타내는 다음 공식임을 우리는 알고 있다.

PI^2 = PI + 1

또한 PSI또한 다음을 만족한다.

PSI^2 = PSI + 1

실제로 PI와 PSI 는 X^2 - x - 1 = 0 을 만족하는 X의 서로 다른 두 제곱근이다.
그러므로 Fib(n)은

Fib(n) = ( (PI+1)*PI^(n-2) - (PSI+1)*PSI^(n-2) ) / sqrt(5) = (PI^n - PSI^n) / sqrt(5)

 를 만족함을 알 수 있다.
해당하는 힌트를 이제 증명했다.
PSI값의 실제 값은

-0.61803398874989484820458683436564

이며 이 값의 절대값은 1보다 작으므로
n이 증가할 때 PSI^n은 0에 수렴한다.
따라서 n이 충분히 크다면

Fib(n) = PI^n / sqrt(5)

와 유사한 값을 가지게 된다.