어느날 갑자기 피보나치 수열의 일반항을 구하는 것이 궁금해서 찾아두고, 여기에 제가 살을 몇 개 붙인 내용입니다. 일단 피보나치 수열의 점화식은 아래와 같습니다.

$$ \Large a_{n + 2} = a_{n + 1} + a_n,\ a_1 = 1,\ a_2 = 1 $$


  여기서 두 가지의 방법이 있습니다. 하나는 수열의 특성 방정식을 이용한 풀이와, 또 다른 하나는 고등학교 과정에서(09년 개정 교육과정 이전 점화식 내용) 나오는 트릭을 이용하는 풀이가 있습니다. 순서대로 두 풀이 모두 써보겠습니다.


  일단 먼저 특성 방정식을 사용하는 풀이를 보여드리겠습니다. 이상하게 이 특성 방정식을 이용한 풀이는 특성 방정식이 정확히 무엇인지를 설명하진 않더라고요...ㅇㅂㅇ... 나름 제대로 찾아보려고 해도 잘 안 나와서 위키백과 및 주워들은 것으로 설명을 해보겠습니다. 예를 들어 $a_{n + 2} = pa_{n + 1} + qa_{n}$라는 피보나치 수열과 형태가 같은 어떤 점화식이 있다고 봅시다. 이 점화식은 특성 방정식 $x^2 = px + q$의 해 $\alpha, \beta$를 통해 $a_n = P\alpha^n + Q\beta^n$의 형태로 나타낼 수 있다고 합니다. 한 번 증명을 어느 블로그(클릭!)를 참고해서 써보자면 아래와 같습니다.


일단 특성 방정식의 근과 계수와의 관계를 이용해 아래와 같이 나타낼 수 있습니다.

$$ p = \left(\alpha + \beta\right),\ q = -\alpha\beta $$


따라서 원래의 점화식을 아래와 같이 정리할 수 있습니다.


$$\displaystyle{ i)\ \alpha - \beta \ne 0 \\[10pt] a_{n + 2} = \left(\alpha + \beta\right)a_{n + 1} - \alpha\beta a_n \\[10pt] a_{n + 2} - \alpha a_{n + 1} = \beta\left(a_{n + 1} - \alpha a_n\right),\ a_{n + 2} - \beta a_{n + 1} = \alpha\left(a_{n + 1} - \beta a_n\right) \\[10pt] a_{n + 2} - \alpha a_{n + 1} = \left(a_2 - \alpha a_1\right) \beta^{n - 1}\ \cdots\ A,\ a_{n + 2} - \beta a_{n + 1} = \left(a_2 - \beta a_1\right) \alpha^{n - 1}\ \cdots\ B \\[10pt] B - A\text{ 를 하면},\ \left(\alpha - \beta\right)a_{n + 1} = \left(a_2 - \beta a_1\right) \alpha^{n - 1} - \left(a_2 - \alpha a_1\right) \beta^{n - 1} \\[10pt] \therefore a_n = { a_2 - \beta a_1 \over \alpha - \beta } \alpha^{n - 1} - { a_2 - \alpha a_1 \over \alpha - \beta }\beta^{n - 1} \\[10pt]~\\[10pt] ii)\ \alpha - \beta = 0 \\[10pt] a_{n + 2} = 2 \alpha a_{n + 1} - \alpha^2a_n \\[10pt] a_{n + 2} - \alpha a_{n + 1} = \alpha\left(a_{n + 1} - \alpha a_{n}\right) \\[10pt] a_{n + 1} = \alpha a_n + \left(a_2 - \alpha a_1\right) \alpha^{n - 1} \\[10pt] \therefore a_n = a_1 \alpha^{n - 1} + n\left(a_2 - \alpha a_1\right) \alpha^{n - 2}} $$


이렇게 증명할 수 있고, 이제 이것을 이용해 단번에 피보나치 수열의 점화식을 일반항으로 나타내봅시다.


$$ \text{특성 방정식을 구해보면},\ x^2 - x - 1 = 0 \\[10pt] \therefore \alpha = {1 + \sqrt{5} \over 2},\ \beta = { 1 - \sqrt{5} \over 2} \\[10pt] \alpha \ne \beta \text{ 이므로} \\[10pt] \begin{align*} a_n &= { a_2 - \beta a_1 \over \alpha - \beta } \alpha^{n - 1} - { a_2 - \alpha a_1 \over \alpha - \beta }\beta^{n - 1} \\[10pt] &= { 1 - \beta \over \alpha - \beta } \alpha^{n - 1} - { 1 - \alpha \over \alpha - \beta }\beta^{n - 1} \\[10pt] &= {1 \over \sqrt{5}} \left(\left(1 + \sqrt{5} \over 2\right)^n - \left(1 - \sqrt{5} \over 2\right)^n\right) \end{align*}$$


  그 다음으로 고등학교 과정에 나오는 트릭을 이용해 일반항을 유도해보겠습니다. (사실 특성 방정식 풀이랑 거의 비슷하게 나옵니다) 위의 피보나지 수열 점화식에서 $a_{n + 1}$의 일부를 좌측으로 이항하여 $b_n$ 꼴을 만들어 낼 수 있도록 합니다. 그러면 이제 아래와 같이 결국 특성 방정식에서 나오는 꼴의 점화식이 되기 때문에 이후 과정은 같게 나오고 일반항이 유도가 됩니다.


$$ a_{n + 2} = a_{n + 1} + a_n \\[10pt] a_{n + 2} - \alpha a_{n + 1} = \beta \left(a_{n + 1} + {1 \over \beta} a_n\right)\ (\alpha + \beta = 1) \\[10pt] -\alpha = {1 \over \beta} \\[10pt] \therefore a_{n + 2} = \left(\alpha + \beta\right)a_{n + 1} - \alpha\beta a_n$$


아무튼 이렇게 피보나치 수열의 일반항을 유도해 낼 수 있습니다.


p.s 고등학교 과정 풀이를 유도하다가 아예 $\alpha$ 만 쓰고 풀이를 쭉 전개해봤는데 막 $\alpha^4$이 나오고 그러더라고요 허허.... 위에 풀이 방식대로 하는게 정신건강에 좋습니다.


'수학, 과학 > 수학 이모저모' 카테고리의 다른 글

최단강하곡선 문제(Brachistochrone Problem)  (0) 2017.06.18
피보나치 수열 일반항 유도  (0) 2017.06.04
회전변환  (0) 2017.06.03
MathJax 사용하기  (0) 2017.05.28

+ Recent posts

티스토리 툴바