피보나치 수열

개요

피보나치 수열(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{ n }[/math]제곱을 [math]\displaystyle{ O(\log n) }[/math]번의 곱셈만에 구할 수 있다는 걸 이용하면 된다. 물론 위에 있는 일반항에 대입해 버리면 되지만, 일반항 쪽은 소수점 계산이 필요하기 때문에 정확한 값을 구하기 쉽지 않지만, [math]\displaystyle{ \mathbb{Q} [\sqrt{5}] }[/math]를 구현하면 어떨까 이것을 이용하면 정확하고 빠르게 값을 계산할 수 있다.

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

프로그래밍

프로그래밍 언어를 공부할 때 어떤 함수가 자기 자신을 다시 불러와서 사용하는 재귀함수를 배우면서 간단한 피보나치 수를 구하는 프로그램을 짜보게 되는 경우가 많다. 다만 이때 짜보는 소스 코드는 계산해야하는 값이 늘어나면 이런저런 문제를 일으키므로 현업에서 사용가능한 소스 코드라고 보기는 힘들다. 이에 대한 설명은 여기의 글을 읽어보자.

이걸 써먹거나 응용한 것들

• n명의 사람에게 치킨을 먹일 때 몇 마리를 주문해야하는지 확인하는 일명 피보나치킨

같이 보기

• 뤼카 수열
• 피보나치 소수
• 제켄도르프의 정리