([(n+1)/2]는 (n+1)/2이하의 최대정수) 아주 계산이 복잡하다. 다항방정식 형태로 바꿔서 풀면 쉽다.
제0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 1번째 수를 1로, 2번째 수도 1로 놓고, 3번째 수부터는 바로 앞의 두 수를 더한 수로 정의하는 게 좀더 흔하게 알려져 있는 피보나치 수열이다. 이 둘 사이에는 시작점이 다르다는 정도를 빼면 사실상 동일하다.
피사의 레오나르도로 널리 알려진 레오나르도 피보나치가 1202년 토끼의 번식을 언급하면서 이 수에 대하여 연구했다. 하지만, 피보나치가 최초로 연구한 것은 아니고 인도의 수학자가 최초란 기록이 남아있다. 기원전 450년 핑갈라가 쓴 책에서 최초로 이 패턴이 언급되었고 이후 인도의 수학자들이 이 수에 대하여 연구한 흔적들이 발견되었다. 그 때문에 피보나치도 동방쪽에서 넘어온 정보를 접한 적이 있지 않았을까 생각하는 무리들도 있긴 하나 공식적인 연관성은 불명. 어쨌든 서유럽에서 이 수열을 연구하고 체계화할 수 있는 업적을 세운 것은 피보나치였기 때문에 피보나치 수열이란 이름이 붙게 됐다. 다만 피보나치 수열이란 이름은 19세기가 되어서야 붙여졌다.
실제 피보나치 수열의 점화식은 인도도 그렇고 유럽도 그렇고 일찌감치 알려져 있었으나 피보나치 수의 생성함수는 완전히 정리되기까지 다소 시간이 필요했다. 1765년오일러가 최초로 이 생성함수를 정리하여 발표했으나 당시에는 별로 주목을 받지 못해서 그대로 묻혔다. 이후 1848년 비네가 이 생성함수를 재발견하여 발표했고 결국 피보나치 수의 생성함수는 비네의 식이라 이름이 붙었다. 하지만, 오일러는 수학계에 어마어마한 업적을 남겼기에 비교가 안될 정도로 유명하다는 게 함정이다.
수학의 수열 파트에서 잠시 배우는 수준이지만 컴퓨터 계열로 진학할 경우 정말 질리도록 보게 된다. 프로그래밍 언어에서 재귀함수를 배우게 되면 과제로 반드시 한 번은 하게 된다. 재귀함수로 간단히 구현되지만, 메모이제이션(Memoization) 없이 구현할 경우 실행시간이 안드로메다로 증가하게 된다. 반대로 메모이제이션을 할 경우에는 필요한 메모리가 O(n) 에 비례해지는 단점이 있다. 단순히 직전과 그 전의 값만 저장하는 방식으로 반복문이나 꼬리재귀 최적화가 된 재귀를 할 경우 시간복잡도 O(n)에 공간복잡도 O(1)도 가능하다. 다만, 정말 큰 임의의 n에 대한 피보나치 수를 구해야한다면, 행렬을 이용하여 시간복잡도 O(log n)에 공간복잡도 O(1)로 구현할 수도 있다. 좀더 높은 레벨의 프로그래밍에서는 피보나치 힙(Fibonacci Heap) 같이 자료구조나 알고리즘 최적화에 피보나치 수열의 성질을 우려먹는 경우를 많이 보게 될 것이다.
자연에서 꽃씨의 배열이나 나무가지의 갈라짐 등등으로 빈번하게 등장하고, 피보나치의 문제처럼 실제 생물의 번식을 설명하는 데에도 쓰인다. 이는 황금비의 자기닮음성이나 프랙탈과도 엮인다. 비슷한 맥락으로 주식시장의 변동을 설명하는 엘리어트 파동 이론(Elliott wave theory)에서 출현하기도 한다. 여러 모로 신기한 수열이다.
베리에이션으로 루카스 수열(Lucas Sequence)가 있는데, 초항과 그 다음 항을 0과 1이 아닌 숫자 두 개를 설정하고 Fn+2=Fn+Fn+1대로 따라가면 루카스 수열이다.
수학 귀신에도 꽤나 나온다. 번식하는 토끼의 수를 나타내거나 아래에 나오는 두 항의 비율이 황금비에 근접하는 사실 등.
위에서 언급한 비네의 식에서 피보나치 수열의 일반항을 황금비로 표시할 수 있는데, 황금비를 φ라고 하고 φ′=1−φ 라고 하면 피보나치 수열의 일반항은 다음과 같다.
Fn=(φ−φ′)(φn−φ′n)
φ=21+5인 무리수이고 피보나치 수열의 모든 항은 자연수인걸 감안하면 굉장히 신기한 수열인데, 증명방법은 대략 다음과 같다.
황금비 φ는 정의에 따라 x2−x−1=0의 0보다 큰 근이고, 0보다 작은 근은 φ′라고 하자. 그러면 근과 계수와의 관계에서 φ+φ′=1,φφ′=−1이다.
이를 이용해 Fn=Fn−1+Fn−2를 변형하여 (Fn−φFn−1)=φ′(Fn−1−φFn−2)과 (Fn−φ′Fn−1)=φ(Fn−1−φ′Fn−2)를 얻는다. 각각에서 Fn−1−φFn−2과 Fn−1−φ′Fn−2가 등비수열이고 n=3일때 각각 1−φ=φ′와 1−φ′=φ이다. 이를 이용해 일반항을 구하면 n≥3일 때 Fn−1−φFn−2=φ′n−2이고, Fn−1−φ′Fn−2=φn−2. 양변을 빼서 정리하면 n≥3일 때 Fn−2=φ−φ′φn−2−φ′n−2이므로 n≥1일 때로 정리하면 위의 식이 나온다.
초항과 둘째항을 다른 숫자로 바꾼, 위에서 언급한 루카스 수열에서도 항의 비율의 극한값은 황금비가 된다. 점화식이 동일하니 당연.
인터넷 상에서 피보나치 수열이 치킨수(Fn−1)와 먹을 사람수(Fn)와의 관계를 나타내는데 적절하다는 설이 있다 역시 치킨이다심지어 사람 숫자에 따른 치킨 숫자를 자동으로 알려주는 사이트도 등장했다.1.000.000.001명을 넘기면 원기옥드립을 친다.1과 0으로 된 숫자를 치면 이진수 드립을 친다 그 외에 22 이상의 2로만 이루어진 숫자를 치면 콩진호 사진이 나오는 등 여러 가지 이스터에그가 119개나 있다.은근 찾아보는 재미도 쏠쏠하다. 예를 들면 42를 입력하면 '모인 사람이 이미 세상 모든 문제의 정답'이란 문구와 '깊은 생각(Deep Thought)'이 등장한다. 또한 √2, 원주율, 자연상수 등의 근사값을 입력하면 관련 이스터에그가 나온다. 사이트 이름이 피보나치킨이다 위의 일반항 공식을 이용하면 이 비율은 점차 황금비에 수렴하고 따라서 대략 치킨 1마리가 1.618인분이라는 정말 쓸데없는 결론을 얻는다.그래서 위 계산기에서도 2명까진 그냥 1인1닭 하라고 나온다. 그냥 5마리가 8인분이라고 외우는게 더 편하다.1인1닭을 하는데 1.618인분이면 우린 이미 1인이 아닌거임.
