수학 개념 지도
정수론(Number theory)

피보나치 수열(Fibonacci sequence)

앞의 두 수를 더해 다음 수를 만드는 수열 1, 1, 2, 3, 5, 8, …. 이웃한 두 항의 비는 황금비⁠(golden ratio)⁠로 수렴⁠(convergence)⁠한다.

Fn+1=Fn+Fn−1,Fn=φn−(−1/φ)n5F_{n+1} = F_n + F_{n-1}, \qquad F_n = \frac{\varphi^n - (-1/\varphi)^n}{\sqrt5}

1, 1에서 시작해 앞의 두 수를 더하면 1, 1, 2, 3, 5, 8, 13, …이 나옵니다. 각 수를 한 변으로 하는 정사각형을 차례로 붙여 나가면 직사각형이 계속 커집니다. 개까지 붙여 보세요.

직사각형의 가로세로 비 Fn+1/FnF_{n+1}/F_n은 위아래로 번갈아 흔들리며 φ=1.6180…\varphi = 1.6180\ldots, 황금비로 모입니다. 이 비들이 곧 φ=[1;1,1,… ]\varphi = [1; 1, 1, \dots]의 연분수⁠(continued fraction)⁠ 수렴분수입니다. 그림의 정사각형 채우기를 거꾸로 하면 유클리드 호제법⁠(Euclidean algorithm)⁠이 됩니다. 이웃한 피보나치 수에서는 마지막 단계를 빼면 매번 정사각형이 하나씩만 들어가서, 수의 크기에 비해 호제법이 가장 오래 걸립니다. 호제법이 gcd⁡(Fn+1,Fn)=gcd⁡(Fn,Fn−1)=⋯=gcd⁡(2,1)=1\gcd(F_{n+1}, F_n) = \gcd(F_n, F_{n-1}) = \cdots = \gcd(2, 1) = 1로 내려가니, 이웃한 두 항은 항상 서로소입니다.

이 점화식⁠(recurrence relation)⁠은 행렬⁠(matrix)⁠ 곱셈 하나로 쓸 수 있습니다: . 그러니 FnF_n을 구하는 일은 같은 행렬을 거듭 곱하는 일(행렬의 곱⁠, matrix multiplication⁠)이고, 거듭제곱은 대각화⁠(diagonalization)⁠로 쉬워집니다. 행렬을 곱해도 같은 직선 위에 머물고 λ\lambda배가 될 뿐인 벡터⁠(vector)⁠가 있을 때, 그 배율 λ\lambda를 고유값⁠(eigenvalue)⁠이라 합니다(λ\lambda가 음수면 방향이 뒤집힙니다). 이 행렬의 고유값은 λ2=λ+1\lambda^2 = \lambda + 1의 두 근 φ\varphi와 −1/φ≈−0.618-1/\varphi \approx -0.618입니다. 곱할 때마다 φ\varphi 방향의 성분은 1.618배로 커지고, 다른 성분은 부호가 바뀌며 크기가 0.618배로 줄어듭니다. 그래서 큰 고유값 방향이 점점 지배해 비가 φ\varphi로 가고, 줄어드는 성분의 부호가 번갈아 바뀌는 것이 오른쪽 그림에서 비가 위아래로 흔들리는 이유입니다. 두 고유값으로 FnF_n을 직접 쓴 식이 제목 아래의 Fn=(φn−(−1/φ)n)/5F_n = (\varphi^n - (-1/\varphi)^n)/\sqrt5입니다. 1843년 이 식을 발표한 프랑스 수학자 자크 비네의 이름을 따 비네 공식⁠(Binet's formula)⁠이라 부르지만, 드무아브르가 한 세기 앞서 알고 있었습니다. 피보나치 수는 파스칼의 삼각형⁠(Pascal's triangle)⁠의 얕은 대각선을 더해도 나옵니다.

정의를 그대로 옮긴 재귀⁠(recursion)⁠ 프로그램은 같은 값을 거듭 다시 계산합니다. FnF_n을 구하는 호출 수는 FnF_n 자신과 같은 속도⁠(velocity)⁠, 곧 φn\varphi^n에 비례해 늘지만, 앞의 두 값을 적어 두며 차례로 올라가는 동적 계획법⁠(dynamic programming)⁠은 n걸음이면 끝납니다. 수열 전체를 급수⁠(series)⁠ ∑Fnxn\sum F_n x^n의 계수로 담으면 생성함수⁠(generating function)⁠ x/(1−x−x2)x/(1-x-x^2)가 되고, 여기서도 비네 공식이 나옵니다. 앞의 두 값을 쌍으로 들고 올라가는 방법은 쌍 (Fn,Fn+1)(F_n, F_{n+1})을 (Fn+1,Fn+Fn+1)(F_{n+1}, F_n + F_{n+1})로 미는 함수⁠(function)⁠를 자연수⁠(natural number)⁠ 위에서 접는 것이어서, 앞의 두 값을 보는 재귀도 시작 대수에서 나가는 한 칸짜리 fold로 적힙니다.

관련 인물레오나르도 피보나치요하네스 케플러아브라암 드무아브르앨런 튜링
관련된 시대와 장소르네상스 이탈리아의 대수학 경연
이 개념이 나오는 큰 생각대칭과 불변량표현 바꾸기

이 개념이 나오는 긴 글

미분에서 회전까지 · 5편 · 복소수와 행렬 곱셈은 회전이다 복소수를 곱하는 일과 행렬로 평면을 돌리는 일은 같은 일이다. 확률 도박판에서 온 편지 1654년, 도중에 멈춘 내기의 판돈을 어떻게 나눌까? 두 수학자가 주고받은 편지에서 확률론이 태어났다. 정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다. 계산 이론 기계가 풀 수 없는 문제 모든 수학 문제를 기계적으로 풀 수 있을까? 러셀의 역설에서 괴델과 튜링까지, 그 질문에 대한 답은 '아니오'였고, 그 증명이 컴퓨터를 낳았다. 조합론 세지 않고 세기 시의 운율을 세던 인도의 운율학자부터 오일러의 생성함수까지. 하나하나 늘어놓지 않고 경우의 수를 세는 법은 어떻게 자라났을까?

이 개념 위에 세워진 것

황금비점화식

이 개념을 언급하는 페이지

  • 고유벡터와 고유값

    … 조금이라도 있다면). 그 방향 성분이 매번 가장 많이 늘어나 나머지를 압도하기 때문입니다(대각화).피보나치 수열에서 이웃한 두 항 (F_{n+1}, F_n) 은 행렬 \begin{bmatrix} 1 & 1 \\ 1 & …

  • 대각화와 행렬 거듭제곱

    … 축은 대칭 행렬 A^{\mathsf T}A 의 고유벡터입니다. 이 생각이 여러 분야를 한 번에 설명합니다.피보나치 수열의 이웃한 두 항은 \begin{bmatrix}F_{n+1}\\F_n\end{bmatrix} = …

  • 선형 미분방정식

    … = Ax_n 이 맡습니다. 이때는 e^{\lambda t} 대신 \lambda^n 을 넣어 풉니다.피보나치 수열이 그 예입니다. 원 운동하는 점의 한 좌표만 보면 사인파가 나옵니다. 용수철에 매단 추는 가속도가 …

  • 최대공약수와 유클리드 호제법

    … 두면 a/b 의 연분수가 됩니다. 마지막 단계를 빼면 매번 정사각형이 딱 하나씩만 들어가는 쌍이 이웃한피보나치 수입니다(처음 값 34와 21이 그렇습니다). 수의 크기에 비해 단계가 가장 많은 쌍이 바로 이것이고, …

  • 연분수

    … 1인 황금비는 근사가 가장 느리게 좋아지는, "가장 무리수다운" 수입니다. 그 수렴분수의 분자와 분모는피보나치 수입니다. 유리수는 계수가 유한하고, 무리수는 무한합니다. 유한한 정수 목록은 셀 수 있으니 유리수가 …

  • 황금비

    … 는 분수로 흉내 내기 가장 어려운, 가장 무리수다운 무리수입니다. 수렴분수의 분자와 분모는피보나치 수입니다. 이 성질로 해바라기 씨앗의 배열을 설명하는 모형이 있습니다(1979년 헬무트 포겔이 제안). …

  • 파스칼의 삼각형

    … \equiv 1 이 되는데, 이것이 페르마 소정리입니다. 비스듬한 얕은 대각선을 따라 더하면피보나치 수가 나옵니다. 이 삼각형의 수를 이항계수라고도 부릅니다. 고른 k 개를 늘어놓는 순서까지 따지면 k! …

  • 편집 거리

    … 이웃 칸에서 값을 모아 오는 방식은 파스칼의 삼각형을 채우는 방식, 앞의 두 값을 기억해 두고피보나치 수를 구하는 방식과 같습니다. 편집 거리는 거리 함수입니다. 삽입은 삭제로, 삭제는 삽입으로, 치환은 …

  • 수학적 귀납법

    … = (m+1)^2 이고, 이것이 귀납 단계입니다. 같은 방식으로 등비급수의 합 공식, 이항정리,피보나치 수의 여러 항등식을 증명합니다. 강한 귀납법. 귀납 단계에서 바로 앞 하나가 아니라 1부터 k까지 전부가 …

  • 점화식

    … = a_{n-1} + a_{n-2} 입니다. a_1 = 1,\ a_2 = 2 에서 시작하므로 한 칸 밀린피보나치 수열a_n = F_{n+1} 이 됩니다. 작은 경우의 답으로 큰 경우의 답을 짓는 이 생각이 재귀와 ⟦동적 …

  • 생성함수

    … (1-x)^{-k} 의 x^n 계수입니다. (1+x)^n 의 계수는 물론 이항계수입니다. 점화식 풀기.피보나치 수열의 점화식 F_n = F_{n-1} + F_{n-2}\ (F_0 = 0,\ F_1 = 1) 을 …

  • 알고리즘

    … 닿으면 끝나고, 남은 좌표가 최대공약수입니다. 나머지를 쓰는 방법이 가장 오래 걸리는 입력은 이웃한 두피보나치 수입니다. 몫이 매번 1이라 한 번에 조금씩밖에 줄지 않기 때문입니다. 거꾸로 말하면, 나눗셈을 k번 해야 …

  • 재귀

    … 스택이 넘쳐 프로그램이 오류로 멈춥니다. 같은 작은 문제를 여러 번 부르는 재귀는 금세 느려집니다.피보나치 수F_n = F_{n-1} + F_{n-2} 을 정의대로 재귀 호출하면 호출 수가 F_n 에 비례해 …

  • 동적 계획법

    재귀로 문제를 작은 문제로 쪼개다 보면 같은 작은 문제가 여러 번 다시 나오는 일이 많습니다.피보나치 수F_{30} 을 정의대로 재귀 호출하면 F_{28} 은 두 번, F_{27} 은 세 번 불리는 식으로 …

  • 고정점

    … \approx -0.382 입니다. 1에서 출발하면 2, 3/2, 5/3, 8/5, …가 나오는데, 이것은피보나치 수열의 이웃한 두 항의 비이자 φ의 연분수 근사입니다. |f'(x^*)| = 1 이면 이 어림으로는 판정이 …

  • 정수론

    … 제타 함수⟧, 쌍둥이 소수, 소수 판정으로 이어집니다. 정수 해의 길에는 피타고라스 세 쌍,피보나치 수열, 황금비가 있고, 정수와 실수의 경계에는 무리수와 대수적 수와 초월수가 있습니다. 세는 문제와 …

  • F-대수와 fold: 재귀와 귀납의 범주론

    … 재귀를 한 가지 틀로 모으고, 그 틀의 유일성이 수학적 귀납법이며, 한 단계짜리 점화식과피보나치 수열이 그 가장 작은 예입니다. 가장 작은 고정점을 되풀이로 찾는 방법은 영역 이론에서 끝나지 않는 …

이 페이지가 가리키는 개념

황금비연분수최대공약수와 유클리드 호제법점화식행렬행렬의 곱대각화와 행렬 거듭제곱고유벡터와 고유값아브라암 드무아브르파스칼의 삼각형재귀동적 계획법생성함수F-대수와 fold: 재귀와 귀납의 범주론