점화식

개요 — 동기·문제의식

셈의 기본 원리와 순열과 조합의 도구는 "한 번에" 셀 수 있는 대상에 강하다. 그러나 하노이 탑의 최소 이동 횟수, 연속한 두 개의 0이 없는 비트열의 개수, 계단을 오르는 방법의 수처럼 크기 $n$짜리 문제의 답이 더 작은 문제의 답으로 표현되는 대상이 많다. 이때 자연스러운 언어가 점화식(recurrence relation) — 수열의 항을 앞선 항들로 정의하는 등식 — 이다. 점화식을 세우는 일은 문제의 재귀적 구조를 읽어내는 일이고, 대개 닫힌 공식을 직접 찾는 것보다 훨씬 쉽다.

세우는 것과 푸는 것은 별개의 문제다. $H_n=2H_{n-1}+1$이라는 식은 $H_{64}$를 알려주지 않는다 — 64번 대입해야 한다. 이 장의 목표는 점화식을 닫힌 형태(closed form)로 푸는 체계적 방법이다: 1차는 반복 대입으로, 상수계수 선형 동차 점화식은 특성방정식으로, 비동차는 특수해를 더해서 푼다. 부산물로 피보나치 수의 놀라운 닫힌 공식인 비네 공식을 얻고, 알고리즘 분석에 나오는 분할정복 점화식과 마스터 정리를 맛본다. 여기서 다 풀리지 않는 점화식(예: 카탈란 수)은 다음 장의 생성함수가 처리한다.

직관

점화식은 도미노다. 초기조건이 첫 패를 넘어뜨리고, 점화식이 "앞 패가 넘어지면 다음 패도 넘어진다"를 보장한다 — 그래서 점화식+초기조건은 수열을 유일하게 결정하고, 점화식에 대한 거의 모든 증명이 증명 기법의 수학적 귀납법으로 돌아간다. 반대로 초기조건이 없는 점화식은 수열이 아니라 수열들의 족을 정의한다: $a_n=2a_{n-1}$의 해는 $a_0$ 선택마다 하나씩, 무한히 많다.

선형 동차 점화식을 푸는 열쇠는 "어떤 등비수열이 이 점화식을 만족하는가"라는 질문이다. $a_n=r^n$을 $a_n=c_1a_{n-1}+c_2a_{n-2}$에 대입하면 $r^n=c_1r^{n-1}+c_2r^{n-2}$, 즉 $r^2=c_1r+c_2$ — 수열에 대한 조건이 $r$에 대한 다항방정식 하나로 압축된다. 이것이 특성방정식이다. 게다가 해들의 합과 상수배가 다시 해이므로(선형성), 특성근이 주는 등비수열 몇 개를 찾으면 그 선형결합으로 모든 해를 만들 수 있다. 선형대수의 눈으로 보면 해 전체는 벡터공간이고, 등비수열들은 그 기저다.

정의

점화식과 해

정의. 수열 $\{a_n\}$에 대한 점화식은 $a_n$을 앞선 항 $a_{n-1},\dots,a_{n-k}$ (와 $n$)으로 나타내는 등식이다. 모든 $n\ge k$에서 이 등식을 만족하는 수열을 점화식의 해(solution)라 한다. 처음 몇 항의 값 $a_0,\dots,a_{k-1}$을 지정하는 조건이 초기조건(initial conditions)이다.

상수계수 선형 점화식

정의. 상수 $c_1,\dots,c_k$ ($c_k\ne0$)에 대해 $$a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k}$$ 꼴의 점화식을 $k$차 상수계수 선형 동차(linear homogeneous) 점화식이라 한다. 우변에 $n$만의 함수 $f(n)\not\equiv0$이 더해진 $a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}+f(n)$은 비동차(nonhomogeneous) 점화식이며, $f(n)$을 지운 식을 그 연관 동차 점화식이라 한다. "선형"은 $a_{n-1}^2$이나 $a_{n-1}a_{n-2}$ 같은 항이 없다는 뜻이고, "동차"는 $a_n\equiv0$이 해가 된다는 뜻이다.

특성방정식

정의. 2차 점화식 $a_n=c_1a_{n-1}+c_2a_{n-2}$의 특성방정식(characteristic equation)은 $r^2-c_1r-c_2=0$이고, 그 근을 특성근이라 한다. 일반적으로 $k$차 점화식의 특성방정식은 $r^k-c_1r^{k-1}-\cdots-c_k=0$이다. ($c_k\ne0$이므로 $r=0$은 특성근이 아니다.)

분할정복 점화식

정의. 크기 $n$의 문제를 크기 $n/b$의 부분문제 $a$개로 쪼개고 비용 $f(n)$으로 결합하는 알고리즘의 비용 함수는 분할정복(divide-and-conquer) 점화식 $T(n)=a\,T(n/b)+f(n)$을 만족한다. 항이 $n-1$이 아니라 $n/b$에 걸리므로 선형 점화식과는 다른 부류이며, $n=b^k$로 제한해 다루는 것이 표준이다.

주요 정리

정리 1 (1차 선형 점화식 — 반복 대입). $a_n=ca_{n-1}+d$ ($n\ge1$, $c,d$ 상수)의 해는, $c\ne1$이면 $a_n=c^na_0+d\,\dfrac{c^n-1}{c-1}$, $c=1$이면 $a_n=a_0+dn$이다.

정리 2 (해공간의 구조 — 유일성과 차원). $k$차 상수계수 선형 동차 점화식의 해 전체 집합 $S$는 수열의 덧셈·상수배에 대해 벡터공간을 이루고, 대응 $\Phi:S\to\mathbb{R}^k$, $\Phi(\{a_n\})=(a_0,\dots,a_{k-1})$은 선형 전단사이다. 따라서 $\dim S=k$이고, 초기조건이 주어지면 해는 유일하다.

정리 3 (서로 다른 특성근). $r^2-c_1r-c_2=0$이 서로 다른 두 근 $r_1\ne r_2$를 가지면, 수열 $\{a_n\}$이 $a_n=c_1a_{n-1}+c_2a_{n-2}$의 해일 필요충분조건은 어떤 상수 $\alpha_1,\alpha_2$에 대해 모든 $n\ge0$에서 $a_n=\alpha_1r_1^n+\alpha_2r_2^n$인 것이다.

정리 4 (중근). 특성방정식이 중근 $r_0$을 가지면(즉 $c_1=2r_0$, $c_2=-r_0^2$, $r_0\ne0$), 일반해는 $a_n=(\alpha_1+\alpha_2n)\,r_0^n$이다.

정리 5 (비네 공식, Binet). 피보나치 수열 $F_0=0$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$에 대해, $\varphi=\frac{1+\sqrt5}{2}$, $\psi=\frac{1-\sqrt5}{2}$라 하면 $$F_n=\frac{\varphi^n-\psi^n}{\sqrt5}.$$

정리 6 (비동차 점화식의 해 구조). 비동차 점화식 $a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}+f(n)$의 한 해(특수해) $\{p_n\}$을 알면, 모든 해는 정확히 $\{p_n+h_n\}$ ($\{h_n\}$은 연관 동차 점화식의 해) 꼴이다.

정리 7 (마스터 정리 — 간단형). $a\ge1$, $b\ge2$ 정수, $c>0$, $d\ge0$이고 $T(n)=a\,T(n/b)+cn^d$가 $b$의 거듭제곱 $n$에서 성립하면 $$T(n)=\begin{cases}\Theta(n^d) & a<b^d,\\ \Theta(n^d\log n) & a=b^d,\\ \Theta(n^{\log_b a}) & a>b^d.\end{cases}$$

예제

예제 1 (하노이 탑). 원판 $n$개를 규칙(한 번에 한 장, 큰 원판을 작은 원판 위에 못 놓음)대로 다른 기둥으로 옮기는 최소 이동 횟수 $H_n$: 맨 아래 원판을 옮기려면 위의 $n-1$개를 보조 기둥으로 치우고($H_{n-1}$), 맨 아래를 옮기고($1$), 다시 위에 쌓아야 하므로($H_{n-1}$) $H_n=2H_{n-1}+1$, $H_1=1$. 정리 1에서 ($c=2$, $d=1$, $a_0=H_0=0$) $H_n=2^n-1$. $H_{64}=2^{64}-1\approx1.8\times10^{19}$ — 전설대로 1초에 한 장씩 옮기면 우주의 나이를 훌쩍 넘는다.

예제 2 (계단 오르기와 비트열 — 점화식 모델링). 한 번에 1칸 또는 2칸씩 계단 $n$칸을 오르는 방법의 수 $S_n$: 마지막 걸음이 1칸이었으면 $S_{n-1}$가지, 2칸이었으면 $S_{n-2}$가지이므로 $S_n=S_{n-1}+S_{n-2}$, $S_1=1$, $S_2=2$ — 곧 $S_n=F_{n+1}$. 연속한 두 0이 없는 길이 $n$ 비트열의 수도 마지막 비트로 경우를 나누면(1로 끝나면 앞 $n-1$자리 자유, 0으로 끝나면 그 앞이 1이어야 함) 같은 점화식을 얻어 $F_{n+2}$가 된다. 서로 다른 문제가 같은 점화식을 공유하는 것 — 이것이 점화식 모델링의 핵심 감각이다.

예제 3 (서로 다른 근). $a_n=a_{n-1}+2a_{n-2}$, $a_0=2$, $a_1=7$. 특성방정식 $r^2-r-2=(r-2)(r+1)=0$, 근 $2,-1$. 정리 3에서 $a_n=\alpha_12^n+\alpha_2(-1)^n$이고 $\alpha_1+\alpha_2=2$, $2\alpha_1-\alpha_2=7$에서 $\alpha_1=3$, $\alpha_2=-1$. 답: $a_n=3\cdot2^n-(-1)^n$.

예제 4 (중근). $a_n=6a_{n-1}-9a_{n-2}$, $a_0=1$, $a_1=6$. 특성방정식 $r^2-6r+9=(r-3)^2=0$, 중근 $3$. 정리 4에서 $a_n=(\alpha_1+\alpha_2n)3^n$이고 $\alpha_1=1$, $(\alpha_1+\alpha_2)\cdot3=6$에서 $\alpha_2=1$. 답: $a_n=(1+n)3^n$. ($a_n=\alpha3^n$만으로는 $a_0=1$, $a_1=6$을 동시에 못 맞춘다 — 해공간이 2차원이어야 하는 이유가 여기서 보인다.)

예제 5 (비동차 — 특수해 맞추기). $a_n=3a_{n-1}+2n$. $f(n)=2n$이 1차 다항식이므로 특수해 후보 $p_n=pn+q$를 대입: $pn+q=3(p(n-1)+q)+2n$에서 $n$의 계수 비교로 $p=3p+2$, 상수항 비교로 $q=-3p+3q$ — 즉 $p=-1$, $q=-\frac32$. 정리 6에 의해 일반해는 $a_n=\alpha\cdot3^n-n-\frac32$이고, 초기조건이 $\alpha$를 결정한다(예: $a_1=3$이면 $3\alpha-1-\frac32=3$에서 $\alpha=\frac{11}{6}$).

예제 6 (분할정복 — 병합 정렬과 이진 탐색). 병합 정렬의 비교 횟수는 $T(n)=2T(n/2)+cn$: $a=2$, $b=2$, $d=1$이고 $a=b^d$이므로 마스터 정리의 둘째 경우, $T(n)=\Theta(n\log n)$. 이진 탐색은 $T(n)=T(n/2)+c$: $a=1$, $b=2$, $d=0$, $a=b^d$이므로 $T(n)=\Theta(\log n)$. 반면 $T(n)=3T(n/2)+cn$은 $a=3>2=b^d$이므로 $\Theta(n^{\log_23})\approx\Theta(n^{1.585})$ — 카라추바 곱셈이 학교 곱셈 $\Theta(n^2)$을 이기는 이유다.

흔한 오해와 함정

• "점화식이 수열을 결정한다" — 초기조건 없이는 아니다. $a_n=a_{n-1}+a_{n-2}$의 해는 2차원 공간 전체(정리 2)이고, 피보나치는 그중 $(F_0,F_1)=(0,1)$인 하나일 뿐이다. 같은 점화식에 $(2,1)$을 주면 뤼카 수열이 된다.
• "중근이어도 $a_n=\alpha r_0^n$이면 충분하다" — 그 족은 1차원뿐이라 임의의 초기조건 두 개를 맞출 수 없다(예제 4). 해공간은 항상 차수만큼의 차원을 가지므로(정리 2) $\{nr_0^n\}$이 반드시 필요하다.
• "비동차 특수해 후보는 $f(n)$과 같은 꼴이면 항상 된다" — $f(n)=s^n$에서 $s$가 특성근이면 $q\,s^n$ 대입이 $0=f(n)$이라는 모순을 낳는다. 이때는 $qn\,s^n$(중근이면 $qn^2s^n$)을 써야 한다. 예: $a_n=2a_{n-1}+2^n$의 특수해는 $n2^n$ 꼴.
• "비네 공식에 $\sqrt5$가 있으니 $F_n$이 정수라는 사실과 안 맞는다" — $\varphi^n$과 $\psi^n$의 무리 부분이 정확히 상쇄된다. 오히려 이 공식은 $F_n$이 $\varphi^n/\sqrt5$의 반올림이라는 강한 정보를 준다(정리 5).
• "$a_n=a_{n-1}^2$이나 $a_n=a_{n-1}a_{n-2}$도 선형 점화식이다" — 앞선 항의 곱·거듭제곱이 들어가면 비선형이고, 특성방정식 방법이 통하지 않는다. (다만 $b_n=\log a_n$ 치환으로 선형이 되는 경우는 있다 — 예: $a_n=a_{n-1}^2$은 $b_n=2b_{n-1}$.)
• "마스터 정리는 모든 분할정복 점화식을 푼다" — $T(n)=aT(n/b)+f(n)$ 꼴 중에서도 세 경우 어디에도 안 걸리는 $f$가 있고(예: $f(n)=n\log n$과 $a=b^d$ 경계의 틈), $T(n)=T(n-1)+T(n/2)$처럼 꼴 자체가 다르면 적용 불가. 위 간단형은 $f(n)=cn^d$일 때만 증명했다.

큰 그림 / 연결

점화식은 조합론의 "세로 방향" 도구다: 셈의 기본 원리·순열과 조합·포함–배제의 원리이 크기 $n$을 고정하고 가로로 세는 동안, 점화식은 $n$과 $n-1$ 사이의 재귀 구조를 세로로 읽는다. 실제로 포함–배제의 원리에서 만난 교란순열 $D_n$도 $D_n=(n-1)(D_{n-1}+D_{n-2})$라는 (변수계수) 점화식을 만족하며, 두 접근이 같은 답을 준다. 이 장의 특성방정식 방법은 상수계수 선형이라는 좁은 문을 통과하는 점화식만 풀 수 있다 — 카탈란 수의 $C_n=\sum_k C_kC_{n-1-k}$처럼 비선형이거나 모든 이전 항을 참조하는 점화식은 생성함수의 형식적 멱급수가 필요하고, 그 관점에서 보면 특성방정식은 유리 생성함수의 분모, 정리 3·4의 일반해는 부분분수 전개에 정확히 대응한다. 한편 분할정복 점화식은 알고리즘의 시간복잡도 분석 언어이고, 재귀 트리 그림은 그래프와 트리의 트리가 계산 구조를 조직하는 대표적 사례다.

연습문제

1. $a_n=3a_{n-1}$, $a_0=2$의 닫힌 형태를 구하고 귀납법으로 검증하라.
2. $a_n=2a_{n-1}+3$, $a_0=0$을 반복 대입으로 풀어라(정리 1을 쓰지 말고 직접 전개한 뒤, 정리 1과 일치함을 확인).
3. 한 번에 1칸 또는 2칸 오르는 계단 문제에서 $S_n=F_{n+1}$임을 귀납법으로 증명하라.
4. $a_n=5a_{n-1}-6a_{n-2}$, $a_0=1$, $a_1=0$을 특성방정식으로 풀어라.
5. $a_n=4a_{n-1}-4a_{n-2}$, $a_0=6$, $a_1=8$을 풀어라.
6. $a_n=2a_{n-1}+3^n$, $a_0=1$의 일반해와 초기조건을 맞춘 해를 구하라.
7. $\left|\frac{\psi^n}{\sqrt5}\right|<\frac12$ ($n\ge0$)을 보이고, 이로부터 $F_n$이 $\frac{\varphi^n}{\sqrt5}$에 가장 가까운 정수임을 증명하라.
8. $T(n)=4T(n/2)+n$, $T(n)=4T(n/2)+n^2$, $T(n)=4T(n/2)+n^3$을 각각 마스터 정리로 분류하고, 첫 번째 경우를 $n=2^k$에서 반복 대입으로 직접 확인하라.

관련 개념

• 셈의 기본 원리 — 경우 나누기(합의 법칙)가 점화식 모델링의 출발점
• 순열과 조합 — 파스칼 항등식 $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$도 2변수 점화식
• 포함–배제의 원리 — 교란순열 $D_n$: 닫힌 공식과 점화식의 두 얼굴
• 생성함수 — 특성방정식으로 안 풀리는 점화식(카탈란 수 등)의 일반 해법
• 증명 기법 — 점화식 증명의 엔진인 수학적 귀납법
• 그래프와 트리 — 분할정복의 재귀 트리