점화식(Recurrence relation)

수열을 정하는 방법은 두 가지입니다. n번째 항을 n의 식으로 바로 쓰거나($a_n = 2^n - 1$), 앞의 항들로 다음 항을 만드는 규칙과 처음 몇 항을 주는 것입니다($a_n = 2a_{n-1} + 1,\ a_0 = 0$). 뒤의 것이 점화식입니다. 처음 값에서 규칙을 한 번씩 적용하면 모든 항이 차례로 정해집니다. 모든 n에서 항이 빠짐없이 하나씩 정해진다는 보장은 수학적 귀납법⁠(mathematical induction)⁠에서 나옵니다.

점화식은 세기 문제에서 저절로 나옵니다. 하노이의 탑⁠(Tower of Hanoi)⁠은 기둥 셋 가운데 한 기둥에 크기 순으로 쌓인 원판들을 다른 기둥으로 옮기는 퍼즐로, 한 번에 원판 하나만 옮길 수 있고 큰 원판을 작은 원판 위에 놓을 수 없습니다. 원판 n개를 옮기는 최소 횟수를 $a_n$이라 합시다. 위의 n−1개를 옆 기둥으로 치우고($a_{n-1}$번), 맨 아래 원판을 옮기고(1번), n−1개를 다시 그 위로 옮기면 됩니다($a_{n-1}$번). 이보다 적게는 안 됩니다. 맨 아래 원판이 움직이는 순간에는 나머지 n−1개가 모두 세 번째 기둥에 있어야 하므로, 그 앞뒤로 n−1개를 통째로 한 번씩 옮겨야 하기 때문입니다. 그래서 $a_n = 2a_{n-1} + 1$입니다.

계단 n칸을 한 칸 또는 두 칸씩 오르는 방법의 수는 마지막 걸음이 한 칸인지 두 칸인지로 나누어 $a_n = a_{n-1} + a_{n-2}$입니다. $a_1 = 1,\ a_2 = 2$에서 시작하므로 한 칸 밀린 피보나치 수열⁠(Fibonacci sequence)⁠ $a_n = F_{n+1}$이 됩니다. 작은 경우의 답으로 큰 경우의 답을 짓는 이 생각이 재귀⁠(recursion)⁠와 동적 계획법⁠(dynamic programming)⁠의 뿌리입니다.

아래는 $a_n = p\,a_{n-1} + q\,a_{n-2} + c$ 꼴의 점화식입니다. 에서 시작해 $p =$ , $q =$ , $c =$ 를 바꿔 보세요. $n = 0$부터 까지 그렸고, 마지막 항은 입니다.

특성방정식⁠(characteristic equation)⁠. $c = 0$일 때 $a_n = r^n$ 꼴의 답을 찾아 넣으면 $r^2 = p\,r + q$가 나옵니다. 이 이차방정식의 두 근 $r_1, r_2$가 다르면 모든 답은 $a_n = A r_1^{\,n} + B r_2^{\,n}$이고, A와 B는 처음 두 항으로 정해집니다. 두 근이 같으면(중근⁠(multiple root)⁠ r) $a_n = (A + Bn)\,r^n$입니다. 피보나치 수열에서는 두 근이 황금비⁠(golden ratio)⁠ $\varphi$와 $-1/\varphi$여서 비네 공식⁠(Binet's formula)⁠ $F_n = \bigl(\varphi^n - (-1/\varphi)^n\bigr)/\sqrt5$이 나옵니다. 1843년에 이를 발표한 프랑스의 수학자 자크 비네의 이름이 붙었지만, 드무아브르가 이미 1718년 무렵 이 식을 알고 있었다고 전해집니다. 이런 식에서 항은 결국 크기가 가장 큰 근의 거듭제곱처럼 자랍니다(그 근의 계수가 0이 아니라면). 지금은

근이 실수⁠(real number)⁠가 아닌 복소수⁠(complex number)⁠이면 항이 부호를 바꾸며 출렁입니다('6마디 되풀이'와 '출렁이며 줄어듦', 둘 다 c = 0). 복소수를 거듭제곱하면 극형식⁠(polar form)⁠의 크기는 n제곱이 되고 각은 n배가 되므로, $r^n$은 복소평면⁠(complex plane)⁠에서 원점 둘레를 일정한 각씩 돌며 커지거나 줄어듭니다. 실수 항은 서로 켤레인 두 근의 항이 더해져 허수⁠(imaginary number)⁠ 부분이 지워진 것이라, 그 회전⁠(rotation)⁠의 그림자, 곧 코사인⁠(cosine)⁠ 모양으로 출렁입니다. $c \ne 0$이고 $p + q \ne 1$이면 상수 답 $c/(1-p-q)$를 더해 주면 되고, 하노이의 탑은 $a_n = 2^n - 1$이 됩니다. 삼각수⁠(triangular number)⁠처럼 $p + q = 1$이면 이 분모가 0이 되므로, 상수 대신 n이나 $n^2$에 비례하는 답을 찾아 더합니다. 이 계산은 상수 계수 선형 미분방정식⁠(linear differential equation)⁠에 $e^{rt}$를 넣어 특성방정식을 얻는 것과 똑같은 구조입니다. 행렬⁠(matrix)⁠로 쓰면 $(a_n, a_{n-1})$에 같은 2×2 행렬 $\begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix}$을 거듭 곱하는 것이고(c = 0일 때), 특성방정식의 근은 그 행렬의 고유값⁠(eigenvalue)⁠입니다(대각화⁠, diagonalization⁠).

이어지는 곳. 점화식을 푸는 또 하나의 방법은 수열 전체를 급수⁠(series)⁠의 계수로 담는 생성함수⁠(generating function)⁠입니다. 카탈랑 수⁠(Catalan number)⁠와 교란순열⁠(derangement)⁠의 개수도 점화식을 만족합니다. 알고리즘⁠(algorithm)⁠의 걸음 수는 흔히 $T(n) = 2T(n/2) + n$ 같은 점화식으로 나타납니다. 크기 n인 문제를 절반 크기 두 개로 나눠 풀고, 두 답을 합치는 데 n걸음이 든다는 뜻입니다. 그 답이 $n\log n$ 정도라는 것이 분할 정복⁠(divide and conquer)⁠과 점근 표기법⁠(asymptotic notation)⁠의 기본 계산입니다.

규칙이 일차식이 아니면 사정이 전혀 다릅니다. $x_{n+1} = r x_n(1-x_n)$ 한 줄에서도, r이 4에 가까우면 로지스틱 사상⁠(logistic map)⁠의 혼돈⁠(chaos)⁠, 곧 처음 값의 아주 작은 차이가 금세 완전히 다른 수열로 벌어지는 현상이 나옵니다. 한 단계짜리 점화식 $a_{n+1} = f(a_n)$의 해가 처음 값 하나로 정확히 하나 정해진다는 것은 자연수⁠(natural number)⁠가 시작 대수라는 사실을 풀어 쓴 것입니다. 일차 점화식을 벡터⁠(vector)⁠와 행렬로 키우고 입력을 더한 $h_t = Ah_{t-1} + Bu_t$는 언어 모델⁠(language model)⁠에도 쓰이는 상태 공간 모형⁠(state space model)⁠의 뼈대이고, 과거를 얼마나 오래 기억하는지는 A의 고유값이 정합니다.