detP=α−β=5=0여서 역행렬을 쓸 수 있다. 이제 행렬 거듭제곱의 순서대로 세 단계를 밟는다. 먼저 초기 상태를 새 기저의 좌표로 읽는다.
P−1u0=51(1−1).(3)
곧 u0=51(α,1)T−51(β,1)T이다. 다음으로 두 좌표에 각각 αn,βn을 곱하고, 마지막에 P로 되돌린다.
un=PDnP−1u0=5αn(α1)−5βn(β1).(4)
아랫칸만 읽으면 피보나치 수열의 일반항이다. 이 식을 비네 공식(Binet's formula)이라고 부른다.
Fn=5αn−βn(n≥0).(5)
윗칸은 같은 꼴에서 지수가 하나 큰 (αn+1−βn+1)/5=Fn+1이다. 지수를 n과 n+1 중 무엇으로 쓰는지는 상태의 윗칸·아랫칸 약속이 정한다. n=0이면 (1−1)/5=0, n=1이면 (α−β)/5=1이다.
이계 점화식에서는 특성방정식 t2=t+1의 두 근으로 같은 일반항을 구했다. 행렬로 보면 그 특성방정식이 곧 det(tI−M)=0이고, 처음 두 값으로 상수를 정하던 일이 식 (3)의 초기 좌표 계산이다.
그림 2는 u0와 u1을 두 고유방향으로 나눈 모습이다. M을 한 번 곱하면 (α,1) 방향 성분은 α≈1.618배로 늘어난다. (β,1) 방향 성분은 β≈−0.618배가 되어 반대쪽으로 넘어가며 줄어든다.
그림 2u0=(1,0)을 고유방향 (α,1)과 (β,1)의 두 성분으로 나눈 평행사변형. M을 곱한 u1=(1,1)에서는 첫 성분이 α배, 둘째 성분이 β배가 된다. figures/eigen_decomposition.py
핵심
피보나치 수열은 앞의 두 수를 상태벡터 (Fn+1,Fn)T 하나로 기억하면 행렬 거듭제곱 un=Mnu0가 된다. M을 서로 다른 두 고윳값으로 대각화하면 일반항 (αn−βn)/5를 얻는다.
Q. 피보나치 수열과 황금비는 무슨 관계인가요?
고윳값 α=(1+5)/2≈1.618이 황금비이고, 이웃한 두 항의 비 Fn+1/Fn이 n이 커질수록 α에 가까워진다. 식 (4)에서 βn 항이 작아져 상태벡터가 (α,1) 방향으로 붙기 때문이다. 예를 들어 F11/F10=89/55≈1.6182다.
피보나치 일반항은 왜 무리수에서 정수가 나오나
α와 β가 같은 식 t2=t+1을 만족해 거듭제곱이 피보나치 수로 정리되기 때문이다. λ2을 λ+1로 바꾸는 일을 되풀이하면 다음을 얻는다.
λn=Fnλ+Fn−1(λ=α,β,n≥1).(6)
예를 들어 α3=α(α+1)=α2+α=2α+1이고, F3=2, F2=1과 맞는다. n에서 n+1로 넘어갈 때도 λn+1=Fnλ2+Fn−1λ=Fn+1λ+Fn이 되어 같은 꼴이 유지된다. 식 (6)을 α와 β에 쓰고 빼면 αn−βn=Fn(α−β)=5Fn이다. 그래서 식 (5)의 5는 정확히 지워진다.
음의 고윳값 β≈−0.618은 이 정확한 값을 맞추는 보정항이다. ∣β∣<1이라 βn/5의 크기는 n=0의 1/5≈0.447이 가장 크고 점점 줄어든다. 그래서 Fn은 αn/5를 반올림한 정수와 같다. 예를 들어 α10/5≈55.0036이고 F10=55다.
그림 3은 차이 Fn−αn/5=−βn/5를 단계마다 찍은 것이다. β<0이라 부호가 번갈아 바뀌고, 크기는 0.618배씩 줄며 늘 ±1/2 안쪽에 있다.
그림 3n=0부터 12까지 Fn과 αn/5의 차이. 차이는 −βn/5라서 부호가 번갈아 바뀌며 줄고, 모든 단계에서 ±1/2 안쪽이라 반올림하면 Fn이 된다. figures/binet_error.py
Q. 피보나치 일반항에서 음의 고윳값 β는 버려도 되나요?
아니다. 정확한 일반항에는 βn 항이 필요하다. 버리고 남은 αn/5는 n=0에서 약 0.447이라 F0=0과 다르고, 어떤 n에서도 정수가 아니다. 크기가 작다는 사실은 반올림의 근거일 뿐, 정확한 식에서 지울 근거가 아니다.
Q. 피보나치 일반항을 계산기로 구하면 소수가 나오는데 틀린 건가요?
아니다. 5와 거듭제곱을 소수로 근사해서 생긴 오차이며, 정확한 값은 식 (6)이 보장하는 정수다. 다만 배정밀도 실수로 αn/5를 반올림하면 이 페이지의 검산에서 n=71부터 틀린 정수가 나온다. 큰 n은 식 (7)의 정수 행렬 곱이 안전하다.
피보나치 행렬의 거듭제곱에는 어떤 수가 들어 있나
Mn의 네 성분이 모두 피보나치 수다. 첫 열은 Mn(1,0)T=un이다. 둘째 열은 M(0,1)T=(1,0)T=u0이므로 Mn−1u0=un−1이다.
Mn=(Fn+1FnFnFn−1)(n≥1).(7)
케일리–해밀턴 정리로도 같은 결과가 나온다. M은 자신의 특성다항식을 만족하므로 M2=M+I다. 식 (6)에서 λ 자리에 M, 상수 자리에 I를 넣은 Mn=FnM+Fn−1I를 성분으로 적으면 식 (7)이다.
행렬식의 성질에서 곱의 행렬식은 행렬식의 곱이다. detM=−1이므로 detMn=(−1)n이고, 식 (7)의 행렬식과 비교하면 카시니 항등식을 얻는다.
Fn+1Fn−1−Fn2=(−1)n(n≥1).(8)
n=4이면 M4=(5332)이고 5⋅2−32=1=(−1)4이다. 식 (7)은 큰 항을 빨리 구하는 데도 쓴다. M을 네 번 거듭 제곱하면 M16이고, 그 오른쪽 위 성분이 F16=987, 왼쪽 위 성분이 F17=1597이다.
지수를 2의 거듭제곱의 합으로 나누면 다른 n도 빨리 구한다. 20=16+4이므로 M20=M16M4이고, 오른쪽 위 성분이 F20=6765다. 점화식을 19번 더하는 대신 행렬 곱 다섯 번(제곱 네 번과 마지막 곱 한 번)으로 끝난다.
피보나치형 수열의 초기값이 다르면 무엇이 달라질까?
같은 행렬 M을 쓰고 시작 상태만 바뀐다. Gn+2=Gn+1+Gn의 시작 상태가 (G1,G0)T이면 Mn의 두 열을 섞어 Mn(G1,G0)T=G1un+G0un−1이다. 아랫칸을 읽으면 n≥1에서 Gn=G1Fn+G0Fn−1이다.
예를 들어 G0=1,G1=3이면 1,3,4,7,11,…이고 M2(3,1)T=(7,4)T다. 공식으로도 G4=3F4+F3=9+2=11이다. 행렬은 같아도 식 (3)의 초기 좌표가 달라지므로 식 (5)를 그대로 쓸 수는 없다.
계단 오르기 방법의 수는 왜 피보나치 수인가
계단을 한 번에 1칸 또는 2칸씩 오르는 방법의 수 an이 피보나치형 점화식을 따르기 때문이다. 마지막 걸음이 1칸이면 그 앞은 n−1칸을 오른 방법이고, 2칸이면 n−2칸을 오른 방법이다. 두 경우는 겹치지 않으므로 n≥3에서 an=an−1+an−2다.
그림 4는 4칸을 오르는 다섯 가지를 마지막 걸음으로 나눈다. 마지막이 1칸인 세 가지는 3칸을 오르는 방법과, 2칸인 두 가지는 2칸을 오르는 방법과 하나씩 짝지어진다.
그림 4 계단 4칸을 1칸·2칸씩 오르는 다섯 가지를 마지막 걸음으로 나눈 것. 마지막이 1칸인 경우는 3칸을 오르는 방법 수 a3=3, 2칸인 경우는 a2=2와 같아 a4=5가 된다. figures/stair_tilings.py
처음 값은 a1=1, a2=2다. 상태 (a2,a1)T=(2,1)T가 바로 u2이므로 an=Fn+1로 지수가 하나 밀린다. 그래서 4칸은 F5=5가지, 10칸은 F11=89가지다. 식 (7)로 보면 M10의 왼쪽 위 성분이 F11이다.
한 번에 3칸까지 오를 수 있으면 앞의 세 값을 기억해야 하므로 상태가 세 칸, 전이행렬이 3×3이 된다. 이때 n≥4에서 an=an−1+an−2+an−3이고 a1=1, a2=2, a3=4에서 4칸은 7가지다. 몇 칸을 기억해야 하는지가 상태벡터의 크기를 정한다.
피보나치 수열과 행렬의 흔한 오해
Mnu0의 윗칸이 Fn이다. — n=2의 상태는 (2,1)이므로 아랫칸이 F2=1이다. 식 (7)에서도 Fn은 Mn의 오른쪽 위에 있고 왼쪽 위는 Fn+1이다.
초기값이 달라도 같은 일반항이다. — G0=1,G1=3이면 G4=11이지만 F4=3이다. 같은 M이라도 계수는 시작 상태에서 다시 정한다.
직접 해보기
식 (7)로 M6을 적고, M6(1,0)T가 어느 상태인지 말하라.
답 1
F7=13, F6=8, F5=5이므로 M6=(13885)다. 첫 열 (13,8)T=(F7,F6)T가 u6이다.
M2를 계산한 뒤 거듭 제곱해서 M4와 M8을 구하고 F8을 읽어라.
답 2
M2=(2111)이므로 M4=(5332), M8=(34212113)이다. 식 (7)에 따라 오른쪽 위 성분이 F8=21이다.
2026-11-17 · 전수 검수 반영 — 대각화 계산을 초기 좌표·거듭제곱·되돌리기 세 단계로 나눔, 무리수 고윳값에서 정수가 나오는 이유와 반올림, 행렬 거듭제곱의 성분·케일리–해밀턴 유도·카시니 항등식·빠른 거듭제곱, 초기값이 다른 수열의 일반 공식과 계단 오르기 활용, 이계 점화식과의 연결, 황금비·계산기 질문 추가, 연습 교체 (에이전트 수정, 그림 1→4)
2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림