피보나치 수열(Fibonacci Sequence)은 각 항이 앞 두 항의 합으로 정의되는 수열로, 자연과 수학에서 중요한 역할을 한다.
정의
피보나치 수열은 다음과 같이 정의된다.
- F(0) = 0, F(1) = 1
- F(n) = F(n-1) + F(n-2) (n ≥ 2)
즉, 첫 번째와 두 번째 항은 각각 0과 1이며, 이후의 항은 앞의 두 항을 더한 값으로 결정된다.
예시
처음 몇 개의 피보나치 수는 다음과 같다.
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
간혹 1로 시작하는 경우도 있다. 교과서나 책에 따라서 다를 수 있다. 1부터 시작하면 1, 1, 2, 3, 5, 8이 된다.
어차피 점화 관계에 따르면 동일한 수이다. 그리고 정말 간혹하다 1, 2, 3, 5, 8로 바로 나가는 경우도 있는데, 이 또한 큰 문제는 없다. 단 가장 일반적인 경우는 0, 1, 1, 2, 3, 5로 가는 수열이다.
성질
- 황금 비율과의 관계 - 피보나치 수열의 연속된 항들의 비율은 황금 비율(약 1.618)로 수렴한다.
- 점화식 - 피보나치 수열은 F(n) = F(n-1) + F(n-2)라는 점화식을 따른다.
- Binet의 공식 (비네의 식) - 피보나치 수를 직접 계산하는 공식은 다음과 같다.
- F(n) = ( (1 + √5)n - (1 - √5)n ) / (2n * √5)
- = ( (n + √5)n - (n - √5)n ) / √5
- 조합적 해석 - 피보나치 수 F(n)은 1과 2의 블록으로 이루어진 n길이의 계단을 오르는 방법의 수와 같다.
자연과의 연관성
피보나치 수열은 자연에서도 발견된다.
- 해바라기 씨앗 배열, 솔방울의 나선 구조
- 달팽이 껍데기, 은하의 나선형 형태
- 나뭇가지 분기 패턴
예제 코드
피보나치 수열을 구하는 간단한 Python 코드:
def fibonacci(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
for i in range(10):
print(fibonacci(i), end=' ')
출력 결과:
- 0 1 1 2 3 5 8 13 21 34
활용
- 컴퓨터 알고리즘 - 동적 계획법(DP)과 분할 정복 기법에서 활용
- 금융 분석 - 피보나치 되돌림(Fibonacci Retracement) 기법으로 주가 분석
- 그래픽 및 디자인 - 황금 비율을 활용한 레이아웃 구성
같이 보기
참고 문헌
- Fibonacci, L. (1202). Liber Abaci.
- Koshy, T. (2001). Fibonacci and Lucas Numbers with Applications. Wiley.