피보나치 수열(Fibonacci Sequence)의 일반항
피보나치 수열
다음을 만족하는 수열 $ \{ a_n \} $을 피보나치 수열이라고 한다.
\begin{gather*}
a_1 = 1, \ \ a_2 = 1, \ \ a_{n+2} = a_{n+1} + a_{n} \ \ (n = 1, \ 2, \ 3, \ \cdots)
\end{gather*}
피보나치 수열의 일반항
피보나치 수열의 일반항은 다음과 같다.
\begin{gather*}
a_{n} = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right\}
\end{gather*}
증명
점화식 $ a_{n+2} = a_{n+1} + a_{n} $을 다음과 같이 변형한다.
\begin{gather*}
a_{n+2} - \alpha a_{n+1} = \beta ( a_{n+1} - \alpha a_n )
\end{gather*}
전개하면
\begin{gather*}
a_{n+2} = (\alpha + \beta) a_{n+1} - \alpha \beta a_n
\end{gather*}
이고, $ a_{n+2} = a_{n+1} + a_{n} $과 같아야 하므로
\begin{gather*}
\alpha + \beta = 1, \ \ \alpha \beta = -1
\end{gather*}
이다.
\begin{align*}
a_{3} - \alpha a_{2} &= \beta ( a_{2} - \alpha a_{1} ) \\[5px]
a_{4} - \alpha a_{3} &= \beta ( a_{3} - \alpha a_{2} ) \\[5px]
a_{5} - \alpha a_{4} &= \beta ( a_{4} - \alpha a_{3} ) \\[5px]
& \ \ \vdots \\[5px]
a_{n} - \alpha a_{n-1} &= \beta ( a_{n-1} - \alpha a_{n-2} )
\end{align*}
이고, 변변 곱하면
\begin{gather*}
a_{n} - \alpha a_{n-1} = \beta^{n-2} ( a_{2} - \alpha a_{1} )
\end{gather*}
$ a_1 = 1 $, $ a_2 = 2 $, $ 1 - \alpha = \beta $이므로
\begin{gather*}
a_{n} - \alpha a_{n-1} = \beta^{n-1} \ \ \ \ \cdots \ \textrm{①}
\end{gather*}
이다.
마찬가지 방식으로 점화식 $ a_{n+2} = a_{n+1} + a_{n} $을
\begin{gather*}
a_{n+2} - \beta a_{n+1} = \alpha ( a_{n+1} - \beta a_n )
\end{gather*}
으로 변형하면
\begin{gather*}
a_{n} - \beta a_{n-1} = \alpha^{n-1} \ \ \ \ \cdots \ \textrm{②}
\end{gather*}
이다.
①에 $ \beta $를 곱하고
\begin{gather*}
\beta a_{n} - \alpha \beta a_{n-1} = \beta^{n}
\end{gather*}
②에 $ \alpha $를 곱한 후
\begin{gather*}
\alpha a_{n} - \alpha \beta a_{n-1} = \alpha^{n}
\end{gather*}
변변 빼면
\begin{gather*}
(\beta - \alpha) a_n = \beta^n - \alpha^n \ \ \ \therefore \ \ a_n = \frac{\beta^n - \alpha^n}{\beta - \alpha}
\end{gather*}
이다.
$ \alpha + \beta = 1 $, $ \alpha \beta = -1 $이므로 $ \alpha $, $ \beta $는
\begin{gather*}
x^2 - x - 1 = 0
\end{gather*}
의 두 근이고, 근의 공식에 의하여
\begin{gather*}
x = \frac{1 \pm \sqrt{5}}{2}
\end{gather*}
이다.
\begin{gather*}
\alpha = \frac{1 - \sqrt{5}}{2}, \ \ \beta = \frac{1 + \sqrt{5}}{2}
\end{gather*}
로 놓으면
\begin{gather*}
a_{n} = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right\}
\end{gather*}
이다.
