피보나치 수열

• 상위 문서 : 수열
• 하위 문서 : 황금비

Fibonacci Sequence.

1 개요

Fibonacci Sequence. 수학에서 다루는 수열. 이 수열의 항들은 피보나치 수(Fibonacci Number)라 부른다. 다음과 같은 점화식으로 피보나치 수열을 정의할 수 있다.

[math]F_0=0, \ F_1=1, \ F_{n+2}=F_{n+1}+F_{n}[/math]

일반항으로 표현하자면 다음과 같다.
[math]\displaystyle F_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}=\frac{1}{2^{n-1}} \sum_{i=1}^{\left[\frac{n+1}{2}\right]}{_nC_{2i-1} 5^{i-1}}[/math] ([math]\left[\frac{n+1}{2}\right][/math]는 [math]\frac{n+1}{2}[/math]이하의 최대정수)
아주 계산이 복잡하다.

다항방정식 형태로 바꿔서 풀면 쉽다.

제0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다.

1번째 수를 1로, 2번째 수도 1로 놓고, 3번째 수부터는 바로 앞의 두 수를 더한 수로 정의하는 게 좀더 흔하게 알려져 있는 피보나치 수열이다. 이 둘 사이에는 시작점이 다르다는 정도를 빼면 사실상 동일하다.

그 중에서 1000 이하의 수까지만 나열해 보자면,

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

이렇게 간다.

피사의 레오나르도로 널리 알려진 레오나르도 피보나치가 1202년 토끼의 번식을 언급하면서 이 수에 대하여 연구했다. 하지만, 피보나치가 최초로 연구한 것은 아니고 인도의 수학자가 최초란 기록이 남아있다. 기원전 450년 핑갈라가 쓴 책에서 최초로 이 패턴이 언급되었고 이후 인도의 수학자들이 이 수에 대하여 연구한 흔적들이 발견되었다. 그 때문에 피보나치도 동방쪽에서 넘어온 정보를 접한 적이 있지 않았을까 생각하는 무리들도 있긴 하나 공식적인 연관성은 불명. 어쨌든 서유럽에서 이 수열을 연구하고 체계화할 수 있는 업적을 세운 것은 피보나치였기 때문에 피보나치 수열이란 이름이 붙게 됐다. 다만 피보나치 수열이란 이름은 19세기가 되어서야 붙여졌다.

실제 피보나치 수열의 점화식은 인도도 그렇고 유럽도 그렇고 일찌감치 알려져 있었으나 피보나치 수의 생성함수는 완전히 정리되기까지 다소 시간이 필요했다. 1765년 오일러가 최초로 이 생성함수를 정리하여 발표했으나 당시에는 별로 주목을 받지 못해서 그대로 묻혔다. 이후 1848년 비네가 이 생성함수를 재발견하여 발표했고 결국 피보나치 수의 생성함수는 비네의 식이라 이름이 붙었다. 하지만, 오일러는 수학계에 어마어마한 업적을 남겼기에 비교가 안될 정도로 유명하다는 게 함정이다.

수학의 수열 파트에서 잠시 배우는 수준이지만 컴퓨터 계열로 진학할 경우 정말 질리도록 보게 된다. 프로그래밍 언어에서 재귀함수를 배우게 되면 과제로 반드시 한 번은 하게 된다. 재귀함수로 간단히 구현되지만, 함수형 언어를 사용하는게 아니라면, 아무 생각 없이 구현했을때 실행시간이 안드로메다로 증가하게 된다. 한번 계산된 것을 저장하고 다시 참조할때는 저장된 값을 사용하는 방법이 필요한데 필요한 메모리가 O(n) 에 비례해지는 단점이 있다. 속도만 따지면 반복문을 이용해서 처음부터 계속 더해서 계산하는게 제일 빠르다.

좀더 높은 레벨의 프로그래밍에서는 피보나치 힙(Fibonacci Heap) 같이 자료구조나 알고리즘 최적화에 피보나치 수열의 성질을 우려먹는 경우를 많이 보게 될 것이다.

자연에서 꽃씨의 배열이나 나무가지의 갈라짐 등등으로 빈번하게 등장하고, 피보나치의 문제처럼 실제 생물의 번식을 설명하는 데에도 쓰인다. 이는 황금비의 자기닮음성이나 프랙탈과도 엮인다. 비슷한 맥락으로 주식시장의 변동을 설명하는 엘리어트 파동 이론(Elliott wave theory)에서 출현하기도 한다. 여러 모로 신기한 수열이다.

베리에이션으로 루카스 수열(Lucas Sequence)가 있는데, 초항과 그 다음 항을 0과 1이 아닌 숫자 두 개를 설정하고 [math] F_{ n + 2 } = F_{ n } + F_{ n + 1 } [/math]대로 따라가면 루카스 수열이다.

2 황금비

피보나치 수열의 항의 비율 [math]\displaystyle \frac{F_n}{F_{n-1}}[/math]의 극한값은 소위 황금비가 된다.

위에서 언급한 비네의 식에서 피보나치 수열의 일반항을 황금비로 표시할 수 있는데, 황금비를 [math]\varphi[/math]라고 하고 [math]\varphi'=1-\varphi[/math] 라고 하면 피보나치 수열의 일반항은 다음과 같다.

[math]\displaystyle F_n=\frac{\left(\varphi^{n}-\varphi'{^n}\right)}{\left(\varphi-\varphi'\right)}[/math]

[math]\displaystyle \varphi=\frac{1+\sqrt{5}}{2}[/math]인 무리수이고 피보나치 수열의 모든 항은 자연수인걸 감안하면 굉장히 신기한 수열인데, 증명방법은 대략 다음과 같다.

황금비 [math]\varphi[/math]는 정의에 따라 [math]x^2-x-1=0[/math]의 0보다 큰 근이고, 0보다 작은 근은 [math]\varphi'[/math]라고 하자. 그러면 근과 계수와의 관계에서 [math]\varphi+\varphi'=1, \varphi\varphi'=-1[/math]이다.

이를 이용해 [math]F_n=F_{n-1}+F_{n-2}[/math]를 변형하여 [math]\left(F_n-\varphi F_{n-1}\right)=\varphi'\left(F_{n-1}-\varphi F_{n-2}\right)[/math]과 [math]\left(F_n-\varphi'F_{n-1}\right)=\varphi\left(F_{n-1}-\varphi'F_{n-2}\right)[/math]를 얻는다. 각각에서 [math]F_{n-1}-\varphi F_{n-2}[/math]과 [math]F_{n-1}-\varphi'F_{n-2}[/math]가 등비수열이고 [math]n=3[/math]일때 각각 [math]1-\varphi=\varphi'[/math]와 [math]1-\varphi'=\varphi[/math]이다. 이를 이용해 일반항을 구하면 [math]n\geq3[/math]일 때 [math]F_{n-1}-\varphi F_{n-2}={\varphi'}^{n-2}[/math]이고, [math]F_{n-1}-\varphi'F_{n-2}=\varphi^{n-2}[/math]. 양변을 빼서 정리하면 [math]n\geq3[/math]일 때 [math]\displaystyle F_{n-2}=\frac{\varphi^{n-2}-{\varphi'}^{n-2}}{\varphi-\varphi'}[/math]이므로 [math]n\geq1[/math]일 때로 정리하면 위의 식이 나온다.

3 음의 피보나치

[math]F_0=0[/math]
[math]F_1=1[/math]
[math]F_n=F_{n-1}+F_{n-2}[/math]

이 식을 바탕으로 하면 [math]F_{-1}[/math]를 비롯해서 음의 피보나치 수를 구할 수 있다.

[math]F_0=0[/math]
[math]F_{-1}=1[/math]
[math]F_{-2}=-1[/math]
[math]F_{-3}=2[/math]
[math]F_{-4}=-3[/math]

피보나치 수열에서 2번에 1번씩 번갈아 부호가 음수가 되는 수열이 만들어진다.

(0), 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, 89, -144, 233, -377, 610, -987

즉, 적당한 [math]k, \ \left(k\gt0\right)[/math]에 대해서 [math]F_{-k}[/math]는 다음과 같은 식을 만족한다.

[math]F_{-k}=\left(-1\right)^{k+1}F_k[/math]

4 치킨과의 상관관계

인터넷 상에서 피보나치 수열이 치킨수([math]F_{n-1}[/math])와 먹을 사람수([math]F_n[/math])와의 관계를 나타내는데 적절하다는 설이 있다 역시 치킨이다심지어 사람 숫자에 따른 치킨 숫자를 자동으로 알려주는 사이트도 등장했다. 사이트 이름이 피보나치킨이다 위의 일반항 공식을 이용하면 이 비율은 점차 황금비에 수렴하고 따라서 대략 치킨 1마리가 1.618인분이라는 정말 쓸데없는 결론을 얻는다. 그냥 5마리가 8인분이라고 외우는게 더 편하다 그냥 1인1닭 하면 된다고

서울대학교 대나무숲 페이지에는 먹을 사람 수가 정확히 피보나치 수열의 [math]F_n[/math]이 되지 않을 때, 제켄도르프(Zeckendorf)의 정리를 이용하면 비교적 적절한 양의 치킨을 알 수 있다고 소개하고 있다.