이 문제는 사실 hint 에 주어진

                        (1)

을 증명하면 되는 문제입니다. Fib(n) 이 가장 가까운 정수라는 말은 수식으로 표현하면,

                       (2)

이 되는 데요.  (1) 식에서

값을 살펴보면 정의에 의해 항상 0.5 보다 작음을 알 수 있습니다.

그러므로 우리는 (1) 식만 증명을 하면 문제가 원하는 증명을 했다고 할 수 있겠네요.

                         (3)

일단 G(n) 이라는 걸 이렇게 정의해 놓고 이것이 피보나치 수열의 특성을 만족시켜주는 지 알아보면 될 것 입니다.

G(0) = 0, G(1) = 1 이라는 것은 간단한 계산을 통해 쉽게 알 수 있습니다.

그럼 G(n) = G(n-1) + G(n-2) 가 성립되는 지 증명만 하면 되겠네요.

위 식에 각각을 대입하여 다시 써보면

이 되고 양변에 2^n 을 곱하면,

  항은 왼쪽으로  항은 오른쪽으로 옮겨서 정리를 해보면

  (4)

이 됩니다. 와 은   이 식의 두 근임을 알 수 있으므로 (4) 식의 각 변을 정리해보면,

좌변

이 되고 우변도 마찬가지로 0 이 되므로 G(n) = G(n-1) + G(n-2) 을 만족함을 알 수 있습니다. 그러므로 G(n)=Fib(n) 이되어 증명이 끝납니다.