피보나치 수

\\(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...\\)

피보나치 수는 다음 점화식으로 정의된다.

\\(F_0 = 0\\)

\\(F_1 = 1\\)

\\(F_i = F_{i-1} + F_{i-2}\qquad(i \ge 2)\\)

보통 피보나치 수를 구할 때 앞에서부터 두항 씩 더해 구해나갈텐데, 다음 성질을 이용해서 구하는 방법도 있다.

피보나치 수는 황금률 \\(\phi\\)와 그 켤레수 \\(\hat{\phi}\\)와 관련이 있다.

\\(\phi\\)와 \\(\hat{\phi}\\)는 다음 방정식의 두 근이다.

\\(x^2 = x + 1\\)

\\(\phi = {1+\sqrt{5} \over 2} \qquad \quad \hat{\phi} = {1-\sqrt{5} \over 2}\\)

두 근에 대해 다음 식이 성립한다.

\\[F_i = {\phi^i - \hat{\phi^i} \over \sqrt{5}}\\]

* 이는 수학적 귀납법으로 증명할 수 있다.

\\(\left\vert \hat{\phi^i} \right\vert < 1\\)이므로 \\({\left\vert \hat{\phi^i} \right\vert \over \sqrt{5}} < {1 \over \sqrt{5}} < {1 \over 2}\\)이고, 따라서 다음과 같음을 알 수 있다.

\\[F_i = \left\lfloor {\phi^i \over \sqrt{5}} + {1 \over 2} \right\rfloor\\]

즉, \\(F_i\\)는 \\(\phi^i / \sqrt{5}\\)를 가장 가까운 정수로 반올림한 값과 같다.

따라서 피보나치 수는 지수적으로 증가한다.