피보나치수열의 일반항

피보나치수열은 초등학생도 흔히 접하는 매우 간단한 형태의 수열이다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

 

피보나치수열을 수학적으로 쓰면 다음과 같다.

초기 조건: $F_1=1$, $F_2=1$

점화식: $F_n=F_{n-1}+F_{n-2}$($n\geq 3$)

 

이 정도면 피보나치수열을 사용하는 데는 부족함이 없지만 큰 피보나치수, 가령 $F_{50}$을 계산하기엔 노가다가 심하다.

따라서 이번에는 피보나치수열의 일반항을 구해볼 것이다.

---

이 글을 읽기 전 동차점화식의 일반항을 먼저 읽어주세요! 이 글에서는 해당 개념을 응용할 것입니다.

 

항 3개를 사용하는 동차점화식의 일반형은 다음과 같다.

$a_n=pa_{n-1}+qa_{n-2}$

 

따라서 피보나치수열은 여기서 $p=q=1$인 형태로 볼 수 있다.

얘를 가지고 우변을 이항해서 =0 꼴을 만들면 다음과 같다.

$F_n-F_{n-1}-F_{n-2}=0$

 

이 식을 특성방정식으로 만들어서 근의 공식으로 근을 구하면 다음과 같다.

$C(x)=x^2-x-1=0$

두 근=$\frac{1\pm \sqrt{5}}{2}$

 

두 근이 다르니까 일반항의 공식 $a_n=P_0\alpha^n+P_1\beta^n$에 대입해서 일반항을 구하면 다음과 같다.

$F_n=P_0\left(\frac{1+\sqrt5}{2}\right)^n+P_1\left(\frac{1-\sqrt5}{2}\right)^n$

 

이제 초기조건을 대입해서 $P_0$와 $P_1$을 계산하면 된다.

$n=1$ → $F_1=P_0\left(\frac{1+\sqrt5}{2}\right)+P_1\left(\frac{1-\sqrt5}{2}\right)=1$

$n=2$ → $F_2=P_0\left(\frac{1+\sqrt5}{2}\right)^2+P_1\left(\frac{1-\sqrt5}{2}\right)^2=1$

 

두 경우에서 나온 식을 각각 정리해서 연립방정식의 형태로 쓰면 다음과 같다.

$\left\{\begin{matrix}\frac{1}{2}(P_0+P_1)+\frac{\sqrt5}{2}(P_0-P_1)=1\\\frac{3}{2}(P_0+P_1)+\frac{\sqrt5}{2}(P_0-P_1)=1\end{matrix}\right.$

 

두 식을 빼주면 $P_0+P_1=0$이 된다. 이 결과와 이를 이항한 $-P_1=P_0$를 위의 두 식중 하나에 대입해서 한 개의 문자로 정리하면 다음과 같다.

$\frac{\sqrt5}{2}(2P_0)=1$, $P_0=\frac{1}{\sqrt5}$

 

$P_0$를 아니까 $P_1$까지 구할수 있다. 두 문자의 값을 앞선 점화식에 대입하면 다음과 같다.

$F_n=\frac{1}{\sqrt5}\left(\frac{1+\sqrt5}{2}\right)^n-\frac{1}{\sqrt5}\left(\frac{1-\sqrt5}{2}\right)^n$

 

따라서 피보나치수열의 일반항은 다음과 같다.

$F_n=\frac{1}{\sqrt5}\left\{\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right\}$

 

---

이번 글에서는 동차점화식의 일반항에서 다룬 내용을 실제로 피보나치수열에 적용한 것으로 거듭 말하지만 우선 동차점화식의 일반항 글을 이해하는 것이 중요하다.

참고로 피보나치수열의 일반항을 알아둘 필요는 없다. 정말 쓸데없다. 앞에서 큰 수의 피보나치 값을 계산하기 힘들어서 일반항을 만들었다고 했는데, 일반항에도 $n$제곱이 들어가 있어 계산이 복잡한 건 마찬가지이다. 그냥 이런 것도 있다는 정도만 알아두자.

 

위의 일반항으로 구한 $F_{50}$의 값은 "12586269025"이다.