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*}$$

이다.