피보나치 수열의 일반항 유도
정리
시퀀스 $\left\{ F_{n} \right\}_{n=0}^{\infty}$ 이 $F_{n+1} := F_{n} + F_{n-1}$ 과 같이 정의되어있다고 하자. $F_{0} = F_{1} = 1$ 이면 $\displaystyle r_{0} : = {{1 + \sqrt{5} } \over {2}}$ 와 $\displaystyle r_{1} : = {{1 - \sqrt{5} } \over {2}}$ 에 대해 $$ F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} $$
설명
- 위에서 소개된 피보나치 수열은 제$0$항부터 시작하는 것에 주의하자.
피보나치 수열의 일반항은 비네 공식binet formula이라 부르기도 한다. 피보나치 수열은 워낙 많은 성질을 가지고 있고 생각지도 못한 부분에서 응용이 되기도 한다. 아예 피보나치 수열만 가지고 책이 나와있는 수준이고, 교과서나 인터넷에도 설명이 많으므로 일단 생략하기로 한다.
유도
방정식 $$ \begin{align*} & r^2 - r - 1 \\ =& \left( r - {{1 + \sqrt{5} } \over {2}} \right) \left( r - {{1 - \sqrt{5} } \over {2}} \right) \\ =& ( r - r_{0} ) ( r - r_{1} ) \end{align*} $$ 을 생각해보자. 위 방정식에 따르면 $$ {r_{0}}^2 - {r_{0}} - 1 = 0 \\ {r_{1}}^2 - {r_{1}} - 1 = 0 $$ 이 성립한다. 조금 더 보기 좋게 바꾸면 $$ {r_{0}}^2 = {r_{0}} + 1 \\ {r_{1}}^2 = {r_{1}} + 1 $$ 이다. 이제 수학적 귀납법을 사용해 $$ F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} $$ 이 참임을 보일 것이다.
$n=0$ 일 때, $$ F_{0} = {{ {r_{0}}^{0+1} - {r_{1}}^{0+1} } \over { r_{0} - r_{1} }} = 1 $$
$n=1$ 일 때, $$ F_{1} = {{ {r_{0}}^{1+1} - {r_{1}}^{1+1} } \over { r_{0} - r_{1} }} = 1 $$
$n=k$ 일 때 $$ F_{k} = {{ {r_{0}}^{k+1} - {r_{1}}^{k+1} } \over { r_{0} - r_{1} }} $$ 이 성립한다고 가정해보자.
$\left\{ F_{k} \right\}$ 는 피보나치 수열이므로
$$ \begin{align*} F_{k+1} =& F_{k} + F_{k-1} \\ =& {{ {r_{0}}^{k+1} - {r_{1}}^{k+1} } \over { r_{0} - r_{1} }} + {{ {r_{0}}^{k} - {r_{1}}^{k} } \over { r_{0} - r_{1} }} \\ =& {{ {r_{0}}^{k} ( r_{0} + 1 ) - {r_{1}}^{k} ( r_{1} + 1 ) } \over { r_{0} - r_{1} }} \\ =& {{ {r_{0}}^{k} \cdot { r_{0} }^{2} - {r_{1}}^{k} \cdot { r_{1} }^{2} } \over { r_{0} - r_{1} }} & \because {r_{0}}^2 = {r_{0}} + 1, {r_{1}}^2 = {r_{1}} + 1 \\ =& {{ {r_{0}}^{k+2} - {r_{1}}^{k+2} } \over { r_{0} - r_{1} }} \end{align*} $$ 정리하면 $$ F_{k+1} = {{ {r_{0}}^{k+2} - {r_{1}}^{k+2} } \over { r_{0} - r_{1} }} $$ 인데, 이는 $$ F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} $$ 이 $n=k+1$ 일때도 성립한 것이다.
■