정의 피보나치 수열은 다음과 같이 정의됩니다:
F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}.
이 수열의 처음 몇 항은 다음과 같습니다:
0, ~ 1, ~ 1, ~ 2, ~ 3, ~ 5, ~ 8, ~ 13, ~ 21, ~ 34[…]
역사 이 수들은 1202년에 처음 도입되었습니다. 이 수들을 도입한 사람은 레오나르도 피보나치(Leonardo Fibonacci)(피사의 레오나르도(Leonardo Pisano)로도 알려져 있음)입니다. 그러나 “피보나치 수"라는 이름이 널리 쓰이게 된 것은 바로 19세기 수학자 뤼카(Lucas) 덕분입니다.
그런데 인도 수학자들은 이보다 더 일찍 이 수열의 수를 언급했습니다. 고팔라(Gopala)는 1135년 이전에, 헤마찬드라(Hemachandra)는 1150년에 언급했습니다.
자연 속의 피보나치 수 피보나치 자신은 다음과 같은 문제와 관련하여 이 수들을 언급하였습니다. “어떤 사람이 사방이 벽으로 둘러싸인 우리에 토끼 한 쌍을 넣었습니다. 매달 두 번째 달부터 각 토끼 쌍이 한 쌍씩 새끼를 낳는다고 할 때, 이 한 쌍의 토끼는 1년 동안 몇 쌍의 토끼를 낳을 수 있겠습니까?”. 이 문제의 답이 바로 지금 그의 이름을 따서 불리는 수열의 수들입니다. 하지만 피보나치가 묘사한 상황은 실제 자연이라기보다는 머릿속 놀이에 가깝습니다.
인도의 수학자 고팔라와 헤마찬드라는 시에서 긴 음절과 짧은 음절, 또는 음악에서 강박과 약박이 교대로 나타나며 만들어지는 리듬 패턴의 개수와 관련하여 이 수열의 수들을 언급했습니다. 전체 n박으로 이루어진 이러한 패턴의 개수는 F_n과 같습니다.
피보나치 수는 자연에서 나타나는 수에 대해 고찰한 케플러의 1611년 저작(“육각형 눈송이에 관하여”)에도 등장합니다.
흥미로운 예로 서양톱풀이라는 식물이 있는데, 이 식물의 줄기 수(따라서 꽃의 수)는 항상 피보나치 수입니다. 그 이유는 간단합니다. 처음에는 줄기가 하나뿐이지만, 이 줄기가 둘로 나뉘고, 이어서 주 줄기에서 또 하나가 갈라져 나오며, 그다음에는 처음 두 줄기가 다시 가지를 치고, 그다음에는 마지막 두 줄기를 제외한 모든 줄기가 가지를 치는 식으로 계속됩니다. 이와 같이 각 줄기는 생겨난 뒤 한 번의 분기를 “건너뛰고”, 그 이후로는 매 분기 단계마다 갈라지기 시작하며, 그 결과로 피보나치 수가 나타납니다.
일반적으로 많은 꽃(예를 들어 백합)의 꽃잎 수는 어떤 피보나치 수입니다.
식물학에서는 ‘‘엽서’’ 현상도 알려져 있습니다. 예로 해바라기 씨앗의 배열을 들 수 있습니다. 씨앗의 배열을 위에서 내려다보면 (서로 겹쳐 놓은 듯한) 두 계열의 나선을 동시에 볼 수 있는데, 한쪽은 시계 방향으로, 다른 쪽은 반시계 방향으로 감겨 있습니다. 이 나선들의 개수는 34와 55, 또는 89와 144처럼 연속한 두 피보나치 수와 대략 일치합니다. 비슷한 사실이 다른 몇몇 꽃에도 성립하며, 솔방울, 브로콜리, 파인애플 등에도 성립합니다.
많은 식물(일부 자료에 따르면 그중 90%)에 대해서는 다음과 같은 흥미로운 사실도 성립합니다. 어떤 잎 하나를 골라, 그 잎에서부터 줄기 위에 정확히 같은 방식으로 배치된(즉, 정확히 같은 방향을 향한) 잎에 도달할 때까지 아래로 내려가 봅시다. 그러면서 도중에 만난 잎들(즉, 높이상 시작 잎과 끝 잎 사이에 위치한 잎들) 가운데 다르게 배치된 잎을 모두 세어 봅시다. 잎들에 번호를 매기는 동안 우리는 점차 줄기 주위를 돌게 됩니다(잎은 줄기 위에 나선형으로 배치되어 있기 때문입니다). 시계 방향으로 도는지 반시계 방향으로 도는지에 따라 회전 수는 서로 다르게 나옵니다. 그런데 시계 방향으로 돈 회전 수, 반시계 방향으로 돈 회전 수, 그리고 만난 잎의 수가 연속된 피보나치 수 3개를 이룬다는 사실이 밝혀졌습니다.
다만 위에서 설명한 방식으로 세어 보면 전혀 다른 수열의 수가 나오는 식물도 있다는 점에 유의해야 합니다. 따라서 엽서(phyllotaxis) 현상을 법칙이라고 할 수는 없으며, 오히려 흥미로운 경향이라고 보는 편이 맞습니다.
성질 피보나치 수는 흥미로운 수학적 성질을 많이 가지고 있습니다.
그중 몇 가지만 소개하면 다음과 같습니다:
카시니 항등식: F_{n+1} F_{n-1} - F_n^2 = (-1)^n.
“덧셈” 규칙: F_{n+k} = F_k F_{n+1} + F_{k-1} F_n.
앞의 등식에서 k = n으로 두면 다음이 성립합니다: F_{2n} = F_n (F_{n+1} + F_{n-1}).
앞의 등식으로부터 귀납법을 이용하면 F_{nk}가 항상 F_n의 배수임을 얻을 수 있습니다.
앞의 명제의 역도 성립합니다. F_m이 F_n의 배수이면 m은 n의 배수입니다.
최대공약수 등식: {\rm gcd} (F_m, F_n) = F_{{\rm gcd} (m, n)}.
유클리드 알고리즘과 관련하여 피보나치 수는 이 알고리즘에 대해 최악의 입력 데이터가 된다는 주목할 만한 성질을 가지고 있습니다(유클리드 알고리즘의 “라메 정리"를 참고하십시오). 피보나치 기수법 제켄도르프 정리는 임의의 자연수 n을 피보나치 수의 합으로 유일하게 나타낼 수 있다고 말합니다:
N = F_{k_1} + F_{k_2} + \ldots + F_{k_r}
여기서 k_1 \ge k_2+2, k_2 \ge k_3+2, \ldots, k_r \ge 2입니다(즉, 표기에서 서로 인접한 두 피보나치 수를 사용할 수 없습니다).
이로부터 모든 수는 피보나치 기수법으로 유일하게 나타낼 수 있다는 것을 알 수 있습니다. 예를 들면 다음과 같습니다.
9 = 8+1 = F_6 + F_1 = (10001)_F, 6 = 5+1 = F_5 + F_1 = (1001)_F, 19 = 13+5+1 = F_7 + F_5 + F_1 = (101001)_F,
또한 어떤 수에서도 1이 두 개 연속으로 나올 수 없습니다.
피보나치 진법에서 수에 1을 더하는 규칙도 어렵지 않게 얻을 수 있습니다. 최하위 자릿수가 0이면 이를 1로 바꾸고, 1이면(즉, 끝이 01이면) 01을 10으로 바꿉니다. 그런 다음 모든 곳에서 011을 100으로 차례대로 고쳐 표기를 “바로잡습니다”. 그 결과 선형 시간에 새로운 수의 표기를 얻게 됩니다.
수를 피보나치 기수법으로 변환하는 것은 간단한 “탐욕” 알고리즘으로 이루어집니다. 피보나치 수를 큰 것부터 작은 것 순으로 차례로 살펴보면서, 어떤 F_k \le n이면 F_k는 수 n의 표현에 포함되므로 n에서 F_k를 빼고 탐색을 계속합니다.
n번째 피보나치 수의 공식 근호를 이용한 공식 프랑스 수학자 비네(Binet)의 이름을 딴 놀라운 공식이 있는데, 이 공식은 그보다 앞서 드무아브르(Moivre)에게 이미 알려져 있었습니다:
F_n = \frac{ \left( \frac{1+\sqrt{5}}{2} \right)^[…]
이 공식은 귀납법으로 쉽게 증명할 수 있지만, 생성 함수의 개념을 이용하거나 함수 방정식을 풀어서 유도할 수도 있습니다.
두 번째 항은 절댓값이 항상 1보다 작으며, 더 나아가 매우 빠르게(지수적으로) 감소한다는 것을 바로 알 수 있습니다. 따라서 첫 번째 항의 값이 “거의” F_n의 값을 준다는 것이 따라 나옵니다. 이를 엄밀한 형태로 쓰면 다음과 같습니다:
F_n = \left[ \frac{ \left( \frac{1+\sqrt{5}}{2} \r[…]
여기서 대괄호는 가장 가까운 정수로의 반올림을 나타냅니다.
그러나 이 공식들은 분수를 매우 높은 정밀도로 다뤄야 하므로 실제 계산에 적용하기에는 그다지 적합하지 않습니다.
피보나치 수에 대한 행렬 공식 다음 행렬 등식은 어렵지 않게 증명할 수 있습니다:
\pmatrix{ F_{n-2} & F_{n-1} \cr } \cdot \pmatri[…]
그런데 그러면 다음과 같이 표기하면
P \equiv \pmatrix{ 0 & 1 \cr 1 & 1 \cr },
다음을 얻습니다:
\pmatrix{ F_0 & F_1 \cr } \cdot P^n = \pmatrix{[…]
따라서 n번째 피보나치 수를 구하려면 행렬 P를 n제곱하면 됩니다.
행렬의 n제곱은 O (\log n)에 계산할 수 있다는 점을 떠올리면(참고: 이진 거듭제곱), n번째 피보나치 수는 정수 연산만으로 O (\log n)에 쉽게 계산할 수 있습니다.
모듈러에 대한 피보나치 수열의 주기성 어떤 모듈러 p에 대한 피보나치 수열 F_i를 생각해 봅시다. 이 수열이 주기적이며, 그 주기가 F_1=1부터 시작한다는 것(즉, 전주기에는 F_0만 포함된다는 것)을 증명하겠습니다.
귀류법으로 이를 증명하겠습니다. 모듈로 p로 취한 피보나치 수의 쌍 p^2+1개를 생각해 봅시다:
(F_1,F_2),\ (F_2,F_3),\ \ldots,\ (F_{p^2+1},F_{p^2[…]
p를 법으로 하는 서로 다른 쌍은 p^2개뿐이므로, 이 수열 안에는 같은 쌍이 적어도 두 개 존재합니다. 이것만으로도 수열이 주기적임을 알 수 있습니다.
이제 이러한 같은 쌍들 가운데 번호가 가장 작은 두 개의 같은 쌍을 고릅시다. 이 쌍들을 어떤 번호를 가진 쌍 (F_a,F_{a+1})과 (F_b,F_{b+1})이라고 합시다. a=1임을 증명합시다. 실제로, 그렇지 않다면 이들에 대해 이전 쌍 (F_{a-1},F_a)와 (F_{b-1},F_b)가 존재하며, 피보나치 수의 성질에 의해 이 쌍들 역시 서로 같게 됩니다. 그러나 이는 우리가 번호가 가장 작은 일치하는 쌍들을 골랐다는 사실에 모순되므로, 증명이 끝났습니다.