피보나치 수열

개요

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

1, 1, 2, 3, 5, 8, 13, 21, 34, ... (OEIS의 수열 A45)

첫항에 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]이다.

아이디어

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

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

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

특징

황금비

[math]\displaystyle{ \lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = \phi }[/math]이다. 여기의 [math]\displaystyle{ \phi }[/math]는 위의 그거. 황금비라고 부른다.

[math]\displaystyle{ \begin{align} \lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} &= \lim_{n \rightarrow \infty} \frac{a_{n+1}+a_n}{a_{n+1}} &= 1 + \frac{1}{\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n}} \end{align} }[/math]

를 이용하면, [math]\displaystyle{ x = 1+\frac{1}{x} }[/math] 방정식을 푸는 형태가 되어 구할 수 있다.

n번째 항 계산하기

[math]\displaystyle{ A_n = \left[ \begin{array}{cc} a_{n+2} & a_{n+1} \\ a_{n+1} & a_{n} \end{array} \right] }[/math]이라고 하면, [math]\displaystyle{ A_{n+1} = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] A_n }[/math]가 성립한다. [math]\displaystyle{ a_0 = 0 }[/math]이라고 하면, [math]\displaystyle{ A_0 }[/math]도 역시 [math]\displaystyle{ \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] }[/math]가 된다. 이것들을 이용하면, [math]\displaystyle{ A_n = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]^{n+1} }[/math]가 성립함을 알 수 있다.

이 식이 요긴하게 쓸 수 있는데, 큰 [math]\displaystyle{ n }[/math]에 대해서 [math]\displaystyle{ a_n }[/math]을 구할 수 있기 때문이다. 물론, 일반항에 대입해 버리면 되지만, 일반항 쪽은 소수점 계산이 필요하기 때문에 정확한 값을 구하기 쉽지 않지만, 이것을 이용하면 정확하게 값을 계산할 수 있다.

피보나치 수열 뿐만 아니라 점화식이 그 전 항들의 어떤 선형 합, 즉, [math]\displaystyle{ a_{n+k} = \sum_{i=0}^{k-1} c_i a_{n+i} }[/math] 꼴로 나타날 때에는 이런 전개가 가능하다. 그중 가장 간단한게 이거