피보나치 수

$0,1,1,2,3,5,8,13,21,34,55,\dots$

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

$F_0=0$ $F_1=1$ $F_i=F_{i-1}+F_{i-2}(i\ge 2)$

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

피보나치 수는 황금률 $\varphi$와 그 켤레수 $\hat{\varphi }$와 관련이 있다. $\varphi$와 $\hat{\varphi }$는 다음 방정식의 두 근이다. $x^2=x+1$ $\varphi =\frac{1+\sqrt{5}}{2}\hat{\varphi }=\frac{1-\sqrt{5}}{2}$

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

$$F_i=\frac{{\varphi }^i-\widehat{{\varphi }^i}}{\sqrt{5}}$$ * 이는 수학적 귀납법으로 증명할 수 있다.

$\left|\widehat{{\varphi }^i}\right|<1$이므로 $\frac{\left|\widehat{{\varphi }^i}\right|}{\sqrt{5}}<\frac{1}{\sqrt{5}}<\frac{1}{2}$이고, 따라서 다음과 같음을 알 수 있다. $$F_i=\lfloor \frac{{\varphi }^i}{\sqrt{5}}+\frac{1}{2}\rfloor$$ 즉, $F_i$는 ${\varphi }^i/\sqrt{5}$를 가장 가까운 정수로 반올림한 값과 같다. 따라서 피보나치 수는 지수적으로 증가한다.