피보나치 수

\(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}\)를 가장 가까운 정수로 반올림한 값과 같다. 따라서 피보나치 수는 지수적으로 증가한다.