피보나치 수열

개요

피보나치 수열은 다음과 같은 정수의 수열을 말한다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

첫항에 0을 포함시키기도 한다. 이것은 처음의 두 수를 0,1로 선택하냐 1,1로 선택하냐의 차이다.

점화식은 다음과 같다.

• [math]\displaystyle{ a_1 = 1, a_2 = 1 }[/math]
• [math]\displaystyle{ a_{n+2} = a_{n+1} + a_n }[/math]

일반항은 다음과 같다.

• [math]\displaystyle{ a_n = \frac{\phi^n - \psi^n}{\phi - \psi} }[/math]
• [math]\displaystyle{ \phi = \frac{1+\sqrt{5}}{2}, \psi = \frac{1-\sqrt{5}}{2} }[/math], [math]\displaystyle{ \phi, \psi }[/math]는 [math]\displaystyle{ x^2 - x - 1 = 0 }[/math]의 해로 큰 쪽이 [math]\displaystyle{ \phi }[/math], 작은 쪽이 [math]\displaystyle{ \psi }[/math]이다.

아이디어

피보나치는 다음과 같은 상황을 생각했다.

• 첫 달 처음에 갓 태어난 암수 토끼 한 쌍이 있다.
• 토끼는 한 달동안 자라 어른 토끼가 된다.
• 어른 토끼 한 쌍은 그 달 마지막에 암수 토끼 한 쌍을 낳는다.
• 무려 안죽는다

그렇다면 매 달 처음에 토끼가 몇 마리나 있을까에 대해 답을 찾다가 발견한 수열이다.