\\(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}\\)를 가장 가까운 정수로 반올림한 값과 같다.

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

'Algorithm > Theory' 카테고리의 다른 글

5개의 원소를 7번 비교로 정렬하기 / 6번 비교로 중간값 찾기 (+ 상대자 논증)  (0) 2018.05.03
점근적 표기 / 평균 수행 시간 분석  (0) 2018.04.20
Mergesort  (0) 2018.04.17
Quicksort  (0) 2018.04.08
Primality test  (0) 2017.11.19