피보나치 수열이란?
피보나치 수열은 바로 앞의 두 수를 더해 다음 수를 만드는 정수 수열로, 0과 1에서 시작합니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…처럼 이어지죠. 이 수열은 수학뿐 아니라 자연 곳곳에서 발견됩니다. 소라 껍데기의 나선이나 해바라기 씨앗의 배열, 그리고 황금비까지 모두 피보나치와 관련이 있습니다. 이 계산기는 임의의 인덱스 \(n\)에 대한 개별 피보나치 수 \(F_n\)을 알려주거나, 시작 인덱스부터 끝 인덱스까지의 전체 수열을 한 번에 만들어 줍니다.
계산기 사용법
생성 드롭다운에서 모드를 선택하세요. 단일 값을 고르고 인덱스 \(n\)을 입력하면 해당 항 \(F_n\)과 그 점화 단계를 함께 보여 줍니다. 수열을 선택한 뒤 시작 \(n\)과 끝 \(n\)을 입력하면 그 범위(양 끝 포함)에 속한 모든 피보나치 수가 나열됩니다. 인덱스는 양수든 음수든 사용할 수 있으며, 지원 범위는 -200부터 200까지입니다.
공식 풀이
핵심 규칙은 점화식 $$F_n = F_{n-1} + F_{n-2}$$이며, 초기값은 \(F_0 = 0\), \(F_1 = 1\)입니다. \(n\)이 큰 경우에도 정확한 값을 얻기 위해, 이 도구는 부동소수점을 쓰는 비네(Binet) 공식 $$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$$ 대신 임의 정밀도 정수로 반복 계산을 합니다. 비네 공식은 대략 \(n = 71\)을 넘어서면 정확도가 떨어지기 때문이죠. 음수 인덱스는 네가피보나치(negafibonacci) 규칙 $$F_{-n} = (-1)^{n+1} F_n$$을 따릅니다. 그래서 \(F_{-1} = 1\), \(F_{-2} = -1\), \(F_{-3} = 2\), \(F_{-4} = -3\)처럼 부호가 번갈아 나타납니다.
계산 예시
\(F_{15}\)를 구하려면 인덱스 15까지 수열을 차례로 펼쳐 봅니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610. 따라서 \(F_{15} = 610\)이며, 이는 $$F_{14} + F_{13} = 377 + 233 = 610$$과 같습니다.
피보나치 수 참조표 (F0부터 F30까지 및 음의 인덱스)
피보나치 수열은 \(F_0 = 0\), \(F_1 = 1\), \(F_n = F_{n-1} + F_{n-2}\)로 정의됩니다. 이 표는 처음 31개 항을 나타냅니다.
| n | Fn | n | Fn | n | Fn |
|---|---|---|---|---|---|
| 0 | 0 | 11 | 89 | 22 | 17711 |
| 1 | 1 | 12 | 144 | 23 | 28657 |
| 2 | 1 | 13 | 233 | 24 | 46368 |
| 3 | 2 | 14 | 377 | 25 | 75025 |
| 4 | 3 | 15 | 610 | 26 | 121393 |
| 5 | 5 | 16 | 987 | 27 | 196418 |
| 6 | 8 | 17 | 1597 | 28 | 317811 |
| 7 | 13 | 18 | 2584 | 29 | 514229 |
| 8 | 21 | 19 | 4181 | 30 | 832040 |
| 9 | 34 | 20 | 6765 | ||
| 10 | 55 | 21 | 10946 |
음의 인덱스
수열은 \(F_{-m} = (-1)^{m+1} F_m\)을 사용해 거꾸로 확장됩니다. 홀수 \(m\)이면 양수 값이고 짝수 \(m\)이면 음수 값입니다.
| n | Fn | 부호 규칙 (-1)m+1, m = |n| |
|---|---|---|
| -1 | 1 | m = 1, 부호 + |
| -2 | -1 | m = 2, 부호 − |
| -3 | 2 | m = 3, 부호 + |
| -4 | -3 | m = 4, 부호 − |
| -5 | 5 | m = 5, 부호 + |
| -6 | -8 | m = 6, 부호 − |
| -7 | 13 | m = 7, 부호 + |
| -8 | -21 | m = 8, 부호 − |
| -9 | 34 | m = 9, 부호 + |
| -10 | -55 | m = 10, 부호 − |
피보나치 수를 손으로 계산하는 방법
- 두 개의 초기값 \(F_0 = 0\)과 \(F_1 = 1\)에서 시작합니다.
- 앞의 두 항을 더해 다음 항을 구합니다: \(F_2 = F_1 + F_0 = 1\), \(F_3 = F_2 + F_1 = 2\), \(F_4 = 3\), \(F_5 = 5\), 이런 식으로 계속합니다.
- 인덱스 n에 도달할 때까지 반복합니다. \(n = 10\)인 경우: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55이므로 \(F_{10} = 34 + 21 =\) 55입니다.
- 음의 인덱스의 경우, \(m = |n|\)을 구하고 \(F_m\)을 찾은 다음 부호 \((-1)^{m+1}\)을 적용합니다. 예: \(F_{-7} = (-1)^{8} F_7 = (+1)(13) =\) 13. 또 다른 예: \(F_{-6} = (-1)^{7} F_6 = -8\).
- 황금비로 검산하기: \(F_n \approx \varphi^n/\sqrt{5}\). \(n = 10\)인 경우 \(\varphi^{10} \approx 122.99\)이고 \(122.99 / 2.23607 \approx 55.0\)으로 일치합니다. 또한 n이 클 때 \(F_{n+1}/F_n\)은 1.618에 가까워야 합니다.
- 매우 큰 n의 경우, 항을 하나씩 더하는 대신 고속 倍加(fast doubling) 방법을 사용합니다: \(F_{2k} = F_k\,(2F_{k+1} - F_k)\), \(F_{2k+1} = F_k^2 + F_{k+1}^2\). \(k = 5\)로 확인하면: \(F_{10} = F_5(2F_6 - F_5) = 5 \times (16 - 5) = 55\).
값은 빠르게 커집니다. \(F_{100}\)은 이미 21자리이므로 큰 n에는 정확한 정수 연산이 필요합니다(이 계산기는 n이 −200에서 200까지를 지원합니다).
자주 묻는 질문
음수 인덱스도 지원하나요? 네. 네가피보나치 확장을 사용하므로 \(F_{-6} = -8\)처럼 부호가 번갈아 나오는 결과를 얻을 수 있습니다.
n은 얼마까지 가능한가요? 지원 범위는 -200부터 200까지입니다. \(F_{200}\)은 42자리 수이며, 임의 정밀도 정수로 정확하게 계산됩니다.
비네 공식을 쓰면 안 되나요? 비네의 닫힌 형태 공식은 보여 주기에는 우아하지만, 배정밀도 반올림 오차 때문에 \(n\)이 커지면 신뢰하기 어렵습니다. 그래서 정답 계산에는 정확한 정수 반복 계산을 사용합니다.