피보나치 수열

점화식

$F_{n+2}=F_{n+1}+F_{n},\quad F_{0}=0,F_{1}=1$

으로 정의되는 수열을 피보나치 수열(Fibonacci sequence)이라 하고, 피보나치 수열의 항을 피보나치 수(Fibonacci number)라고 한다. 피보나치 수의 일부를 작은 순서대로 나타내면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169 (oeis:A000045)

1202년 레오나르도 피보나치가 이 수열을 기록하였다.

일반항

피보나치 수열의 일반항은

$F_{n}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)$

으로 나타낼 수 있다. 피보나치 수열의 점화식은 선형점화식으로, 피보나치 수열의 특성방정식

$x^{2}-x-1=0$

의 근은 $x={\frac {1+{\sqrt {5}}}{2}}$ 또는 $x={\frac {1-{\sqrt {5}}}{2}}$이다. 이때 ${\frac {1+{\sqrt {5}}}{2}}$는 황금비이다. 따라서

$F_{n}=c_{1}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+c_{2}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}$

인데, $F_{0}=0,F_{1}=1$이므로 일차연립방정식

${\begin{cases}0&=c_{1}+c_{2}\\1&={\frac {1+{\sqrt {5}}}{2}}c_{1}+{\frac {1-{\sqrt {5}}}{2}}c_{2}\end{cases}}$

을 얻는다. 연립방정식을 풀어

$c_{1}={\frac {1}{\sqrt {5}}},c_{2}=-{\frac {1}{\sqrt {5}}}$

를 얻는다.

항등식

• $F_{n-1}F_{n+1}-F_{n}^{2}=(-1)^{n}$ (카시니의 항등식)

같이 보기

• Fibonacci Quarterly