혼자 공부하면서 풀어본 것입니다. 그런만큼 오류가 많을 것이라 생각합니다. 문제 있는 부분은 알려주시면 고맙겠습니다.
Exercise 1.13. Prove that Fib(n) is the closest integer to 
n/
5, where = (1 + 5)/2. Hint: Let 
= (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (n - n)/5.
n/5, where = (1 + 5)/2. Hint: Let = (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (n - n)/5.수학적 귀납법을 통해 증명한다면
Fib(0) = 0
(φ0 － ψ0) / √5
= (1 - 1) / √5 = 0
∵ Fib(0) = (φ0 － ψ0) / √5
Fib(1) = 1
(φ1 － ψ1) / √5
= {(1 + √5) / 2 - (1 - √5) / 2} / √5
= 2√5 / 2√5 = 1
∵ Fib(1) = (φ1 － ψ1) / √5
만약
Fib(n-1) = (φn-1 － ψn-1) / √5
Fib(n) = (φn － ψn) / √5 이 성립한다고 가정하자.
이 때
Fib(n+1) = (φn+1 － ψn+1) / √5 이 성립하는지를 알아봐야 하므로
Fib(n+1)
= Fib(n) + Fib(n-1)
= (φn － ψn) / √5 + (φn-1 － ψn-1) / √5
= {(φn + φn-1) + (ψn + ψn-1)} / √5
= {φn-1(φ + 1) + ψn-1(ψ + 1)} / √5 이 된다.
이 때, φ2 = (3 + √5) / 2 = φ + 1 이고, ψ2 = (3 - √5) / 2 = ψ + 1 이다.
∵ Fib(n+1) = (φn+1 － ψn+1) / √5 이 성립한다.
즉, n = 0 과 n = 1에서 성립하므로 n = 2 이상의 정수에서 Fib(n) = (φn － ψn) / √5 이 성립한다.
따라서 n = 0 이상의 자연수에서
Fib(n) = (φn － ψn) / √5 이 성립함을 증명할 수 있다.
따라서 n = 0 이상의 자연수에서 (φn － ψn) / √5 가 φn / √5 에 가장 가까운 정수라면 이를 증명 가능하다.
-------------------------------2009/01/03 21:47
(φn － ψn) / √5 가 φn / √5 에 가장 가까운 정수이기 위해서는 두가지 조건이 성립되야 한다.
1. (φn － ψn) / √5 가 정수여야 하며,
2. 이 두 숫자의 차가 0.5 미만이어야 한다.
2번이 성립해야 하는 이유는 어떤 정수 a가 가장 가까운 수 x의 범위는
a - 0.5 < x < a + 0.5 이기 때문이다.
따라서 | - ψn / √5 | < 0.5 가 성립하면 증명이 완료된다.
- ψn / √5 = - {(1 - √5) / 2}n / √5
가 된다.
√5 의 값은 2 < √5 <3 이다.
∵ (1 - √5) 의 값은 - 2 < (1 - √5) < - 1
∵ (1 - √5) / 2 의 값은 - 1 < (1 - √5) < - 1 / 2
∵ - ψn은 (- 1)n 과 (- 1 / 2)n 사이에 위치한다.
즉, | - ψn|은 1 이하에서 진동한다.
| - ψn | ≤ 1 로 분자가 1보다 작거나 같지만 분모 | √5 | > 2이므로
- ψn / √5 < 1 / 2 이 항상 성립한다. (더 자세한 증명이 필요한 부분인지 아닌지를 모르겠다.)
따라서 n = 0 이상의 자연수에서
Fib(n) 은 φn / √5 에 가장 가까운 정수임을 증명할 수 있다.
P.S. 이번에 이렇게 오래 풀지 못한 이유는 - ψn / √5 를 구하는데 너무 집착한 나머지 단순히 가깝다는 것의 의미 자체를 생각하면 쉽게 증명할 수 있다는 사실을 깨닫지 못했기 때문이었습니다.
