피보나치 수열의 일반항, fibonacci numbers

피보나치 수열의 일반항

다음과 같은 Fibonacci 수열

$\begin{align*} 1,1,2,3,5,8,13,21,34,\dots \end{align*}$

은 관계식을

$\begin{align*} F_n = F_{n-1} + F_{n-2} \end{align*}$

을 만족한다. 일반항을 구하기 위해

$\begin{align*} F_n = Cx^n \end{align*}$

을 가정한다. 그리고 관계식에 대입하면

$\begin{align*} Cx^n = Cx^{n-1} + Cx^{n-2} \end{align*}$

을 얻는다. 관계식과 같은 계수를 가지는 방정식

$\begin{align*} x^2 = x + 1 \end{align*}$

을 생각한다. 식을 좌변으로 이항하면

$\begin{align*} x^2-x-1=0. \end{align*}$

이 이차방정식의 두개의 해를 근의 공식으로 구하면

$\begin{align*} x=\frac{ -(-1) \pm \sqrt{ (-1)^2-4(1)(-1) } }{2(1)} = \frac{1\pm\sqrt{5}}{2}. \end{align*}$

이것은 두가지 형태의 식

$\begin{align*} F_n = C\left(\frac{1+\sqrt{5}}{2}\right) , C\left(\frac{1-\sqrt{5}}{2}\right), \end{align*}$

그리고 이것의 조합을 일반항

$\begin{align*} F_n = B\left(\frac{1+\sqrt{5}}{2}\right)^n + C\left(\frac{1-\sqrt{5}}{2}\right)^n. \end{align*}$

여기서 $B$와 $C$의 값을 구하기 위해, $F_0=1$ 그리고 $F_1=1$을 대입하면,

$\begin{align*} B\left(\frac{1+\sqrt{5}}{2}\right)^0 + C\left(\frac{1-\sqrt{5}}{2}\right)^0=1, \end{align*}$

$\begin{align*} B\left(\frac{1+\sqrt{5}}{2}\right)^1 + C\left(\frac{1-\sqrt{5}}{2}\right)^1=1. \end{align*}$

식을 간단히 하면

$\begin{align*} F_0 &= B + C= 1 \\ F_1 &= B\left(\frac{1+\sqrt{5}}{2}\right) + C\left(\frac{1-\sqrt{5}}{2}\right) = 1 \end{align*}$

아래식을 정리하면

$\begin{align*} B\left(1+\sqrt{5}\right) + C\left(1-\sqrt{5}\right) &=2\\ B+B\sqrt{5} + C - C\sqrt{5} &=2\\ (B+C) + \left(B - C\right)\sqrt{5} &=2\\ \end{align*}$

$B+C=1$이기 때문에

$\begin{align*} (B+C) + \left(B - C\right)\sqrt{5} = 1+\left(B - C\right)\sqrt{5} &= 2 \\ \left(B - C\right)\sqrt{5} &= 1\\ B-C &= \frac{1}{\sqrt{5}} \end{align*}$

그러므로

$\begin{align*} B+C &= 1\\ B-C &= \frac{1}{\sqrt{5}} \end{align*}$

두식을 더하면

$\begin{align*} 2B = 1+\frac{1}{\sqrt{5}}=\frac{\sqrt{5}+1}{\sqrt{5}} \end{align*}$

이므로

$\begin{align*} B = \frac{\sqrt{5}+1}{2\sqrt{5}}. \end{align*}$

이므로

$\begin{align*} B = \frac{\sqrt{5}+1}{2\sqrt{5}}. \end{align*}$

이므로

$\begin{align*} B = \frac{\sqrt{5}+1}{2\sqrt{5}}. \end{align*}$

이므로

$\begin{align*} B = \frac{\sqrt{5}+1}{2\sqrt{5}}. \end{align*}$

이므로

$\begin{align*} B = \frac{\sqrt{5}+1}{2\sqrt{5}}. \end{align*}$

이것을 $B+C=1$에 대입하면,

$\begin{align*} \frac{\sqrt{5}+1}{2\sqrt{5}}+C &=1\\ C &= 1 - \frac{\sqrt{5}+1}{2\sqrt{5}} = \frac{\sqrt{5}-1}{2\sqrt{5}} \end{align*}$

따라서 Fibonacci 수열의 일반항은

$\begin{align*} F_n &= \frac{\sqrt{5}+1}{2\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{\sqrt{5}-1}{2\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\\ &= \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n.\\ \end{align*}$

이것이 Binet's 공식(비네의 공식) 이다.