9강. 점화식

어떤 수를 직접 세기 어려울 때, 크기 $n$인 경우를 더 작은 경우로 나타내는 식(점화식)을 세우면 쉬워집니다. 이 강에서는 점화식을 세우는 법과, 계수가 상수인 선형 점화식을 닫힌 꼴로 푸는 법을 다룹니다. 풀이 방법은 선형대수의 고윳값과 같은 구조입니다.

9.1 점화식으로 세기

정의 9.1 (점화식). 수열 $a_n$의 항을 앞의 항들로 나타낸 식을 점화식(recurrence relation)이라 하고, 수열을 정하는 데 필요한 처음 몇 항을 초기조건(initial condition)이라 합니다.

예제 9.2 (하노이의 탑). 원판 $n$개를 옮기는 최소 횟수 $H_n$은 “위 $n-1$개를 옆으로, 가장 큰 것을 목표로, $n-1$개를 그 위로” 옮기므로 $H_n = 2H_{n-1} + 1$, $H_1 = 1$입니다. 풀면 $H_n = 2^n - 1$입니다.

예제 9.3 (연속한 1이 없는 비트열). 길이 $n$인 비트열 가운데 1이 연달아 나오지 않는 것의 수를 $a_n$이라 합시다. 마지막 비트가 0이면 앞은 길이 $n-1$인 아무 그런 비트열($a_{n-1}$가지), 1이면 그 앞은 반드시 0이고 그 앞은 길이 $n-2$인 그런 비트열($a_{n-2}$가지)입니다. 그러므로 $a_n = a_{n-1} + a_{n-2}$, $a_1 = 2$, $a_2 = 3$입니다. 피보나치 수열을 두 칸 민 것($a_n = F_{n+2}$)입니다.

9.2 선형 동차 점화식

정의 9.4. 상수 $c_1, \dots, c_k$($c_k \ne 0$)에 대해 $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$ 꼴을 $k$계 선형 동차 점화식이라 합니다.

$a_n = r^n$ 꼴의 해를 찾아봅니다. 넣으면 $r^n = c_1 r^{n-1} + \cdots + c_k r^{n-k}$이고, $r^{n-k}$로 나누면

이 됩니다. 이것을 특성방정식(characteristic equation), 그 근을 특성근(characteristic root)이라 합니다.

정리 9.5 (서로 다른 특성근). 2계 점화식 $a_n = c_1 a_{n-1} + c_2 a_{n-2}$의 특성방정식 $r^2 - c_1 r - c_2 = 0$이 서로 다른 두 근 $r_1$, $r_2$를 가지면, 모든 해는

꼴이고 $\alpha$, $\beta$는 초기조건으로 정해집니다.

증명. $r_1^n$, $r_2^n$이 각각 해이고, 점화식이 선형이므로 그 일차결합도 해입니다. 초기조건 $a_0 = \alpha + \beta$, $a_1 = \alpha r_1 + \beta r_2$는 $r_1 \ne r_2$이면 $\alpha$, $\beta$에 대해 유일하게 풀립니다. 2계 점화식의 해는 $a_0$, $a_1$로 완전히 정해지므로(귀납법) 모든 해가 이 꼴입니다. □

예제 9.6 (피보나치 수의 닫힌 꼴). $F_n = F_{n-1} + F_{n-2}$의 특성방정식은 $r^2 - r - 1 = 0$이고 근은 $\varphi = \frac{1+\sqrt5}{2}$, $\psi = \frac{1-\sqrt5}{2}$입니다. $F_0 = 0 = \alpha + \beta$, $F_1 = 1 = \alpha\varphi + \beta\psi$를 풀면 $\alpha = 1/\sqrt5$, $\beta = -1/\sqrt5$이므로

$|\psi| < 1$이므로 $n$이 크면 $\psi^n$은 무시할 수 있고, $F_n$은 $\varphi^n/\sqrt5$에 가장 가까운 정수입니다. 이웃한 항의 비 $F_{n+1}/F_n$은 황금비 $\varphi \approx 1.618$로 갑니다.

9.3 중근

정리 9.7. 특성방정식이 중근 $r_0$을 가지면 모든 해는 $a_n = (\alpha + \beta n) r_0^n$ 꼴입니다.

증명 개요. $r^2 - c_1 r - c_2 = (r - r_0)^2$이면 $c_1 = 2r_0$, $c_2 = -r_0^2$입니다. $n r_0^n$을 넣으면 $2r_0 (n-1) r_0^{n-1} - r_0^2 (n-2) r_0^{n-2} = (2n - 2 - n + 2) r_0^n = n r_0^n$이므로 해입니다. □

예제 9.8. $a_n = 4a_{n-1} - 4a_{n-2}$, $a_0 = 1$, $a_1 = 4$. 특성방정식 $(r-2)^2 = 0$이므로 $a_n = (\alpha + \beta n)2^n$. $a_0 = \alpha = 1$, $a_1 = 2(1 + \beta) = 4$에서 $\beta = 1$. 그러므로 $a_n = (n+1)2^n$입니다.

9.4 비동차 점화식

$a_n = c_1 a_{n-1} + \cdots + f(n)$처럼 상수가 아닌 항 $f(n)$이 붙으면, 일반해는 (동차 부분의 일반해) + (특수해 하나)입니다. 특수해는 $f(n)$과 같은 꼴로 짐작합니다.

예제 9.9. $H_n = 2H_{n-1} + 1$. 동차해는 $\alpha 2^n$, 상수 특수해 $H = c$를 넣으면 $c = 2c + 1$에서 $c = -1$. 그러므로 $H_n = \alpha 2^n - 1$이고 $H_1 = 1$에서 $\alpha = 1$, 곧 $H_n = 2^n - 1$입니다.

9.5 분할정복 점화식

크기 $n$인 문제를 크기 $n/b$인 문제 $a$개로 나누고 합치는 데 $f(n)$이 드는 알고리즘의 시간은 $T(n) = aT(n/b) + f(n)$을 만족합니다.

예제 9.10 (이진 탐색). $T(n) = T(n/2) + 1$, $T(1) = 1$이면 $n = 2^k$일 때 $T(n) = k + 1 = \log_2 n + 1$입니다.

예제 9.11 (병합 정렬). $T(n) = 2T(n/2) + n$, $T(1) = 0$이면 $n = 2^k$일 때 $T(n) = n\log_2 n$입니다. 양변을 $n$으로 나누면 $T(n)/n = T(n/2)/(n/2) + 1$이므로 $T(n)/n$이 한 번 나눌 때마다 1씩 늘어납니다.

쓰이는 곳. 알고리즘의 실행 시간(분할정복의 $T(n) = 2T(n/2) + n$), 동적 계획법, 인구·금융 모델, 디지털 필터가 점화식입니다. 선형 점화식을 특성근으로 푸는 방법은 선형대수의 고윳값과 같습니다.

9.6 이 장의 요약

• 점화식은 마지막 단계(마지막 원소, 마지막 동작)로 경우를 나눠 세웁니다.
• 선형 동차: 특성방정식의 근 $r_i$로 $a_n = \sum \alpha_i r_i^n$. 중근이면 $n r^n$이 더해집니다.
• 비동차: 동차해 + 특수해.

문제

1023

144

2
-1
454

448

10240