MATH FACTORY

피보나치 수열

다음을 만족하는 수열 $ \{ 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*}

이다.