피보나치 수열

점화식

$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)$

으로 나타낼 수 있다.

같이 보기

• Fibonacci Quarterly