피보나치 수열 생성기

피보나치 수열은 각 항이 앞의 두 항의 합이 되는 수열입니다.

기본 정의

• F(0) = 0, F(1) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 2)
• 수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

황금비 (φ = phi)

• φ = (1 + √5) / 2 ≈ 1.618033988...
• 연속된 두 피보나치 수의 비가 황금비로 수렴
• F(n+1) / F(n) → φ (n이 커질 때)

비네의 공식 (Binet's Formula)

• F(n) = (φⁿ - (-φ)ⁿ) / √5
• 직접 계산 없이 n번째 피보나치 수 계산 가능
• 공식의 정확성은 n이 커질수록 증가

자연에서의 피보나치

• 식물: 꽃잔, 솔방울, 나선형 배열
• 동물: 소라께질, 벌집의 육각형
• 인체: 손가락 비율, 얼굴 비율
• 지질학: 나선형 은하, 바람 패턴

예술과 건축에서의 활용

• 건축: 파르테논 신전, 피라미드
• 디자인: 로고, 레이아웃, 타이포그래피
• 예술: 레오나르다 다 빈치, 모나리자
• 사진: 삼분법 규칙, 구도 비율

수학적 성질

• F(n)² - F(n-1) × F(n+1) = (-1)ⁿ⁻¹ (카시니 항등식)
• 연속된 3개의 피보나치 수로 직각삼각형 만들기 가능
• GCD(F(m), F(n)) = F(GCD(m, n))
• 유클리드 호제법의 최악 사례

컴퓨터 과학에서의 활용

• 알고리즘 분석 (동적 계획법)
• 피보나치 힐 (Fibonacci Heap)
• 피보나치 탐색 (Fibonacci Search)
• 란담 넘버 생성 알고리즘