선형 점화식의 일반항

선형 점화식이란

앞의 몇 항에 상수를 곱해 더한 값으로 다음 항이 정해지는 수열을 상수 계수 선형 점화식(linear recurrence with constant coefficients) 이라 한다.

aₙ = c₁·aₙ₋₁ + c₂·aₙ₋₂ + … + cₖ·aₙ₋ₖ

피보나치 수열(Fₙ = Fₙ₋₁ + Fₙ₋₂)이 대표적이다. 이 노트의 예제는 야콥스탈 수열이다.

a₀ = 0, a₁ = 1, aₙ = aₙ₋₁ + 2·aₙ₋₂
0, 1, 1, 3, 5, 11, 21, 43, 85, …

일반항(closed form)을 알면 n번째 항을 반복 없이 바로 계산하고, 증가 속도(복잡도)를 한눈에 본다. 야콥스탈 수열은 병합 삽입 정렬의 삽입 순서를 정하는 데 쓰인다.

방법 1: 생성함수

생성함수(generating function) 는 수열의 각 항을 계수로 삼는 멱급수다. 주사위 눈의 경우의 수를 x + x² + … + x⁶처럼 지수와 계수로 나타내는 발상과 같다.

G(x) = a₀ + a₁x + a₂x² + … = Σ aₙxⁿ

점화식 양변에 xⁿ을 곱해 n ≥ 2에 대해 모두 더하면 G(x) − x = x·G(x) + 2x²·G(x)가 된다.
정리하면 G(x) = x / (1 − x − 2x²) = x / ((1 − 2x)(1 + x)).
부분분수로 쪼갠다: G(x) = (1/3)·1/(1 − 2x) − (1/3)·1/(1 + x).
1/(1 − rx) = Σ rⁿxⁿ (등비급수)를 적용해 xⁿ의 계수를 읽는다.

aₙ = (2ⁿ − (−1)ⁿ) / 3

생성함수는 수렴 여부를 따지지 않는 형식적 멱급수(formal power series) 로 다루므로 등비급수의 수렴 조건 |rx| < 1을 신경 쓰지 않아도 된다.

방법 2: 특성방정식

상수 계수 선형 점화식의 해는 지수적으로 자란다. 그래서 aₙ = rⁿ을 대입해 본다.

rⁿ = rⁿ⁻¹ + 2rⁿ⁻²   →   r² − r − 2 = 0   →   r = 2 또는 −1

이 이차방정식이 특성방정식(characteristic equation) 이다. 근이 서로 다르면 일반항은 근의 거듭제곱의 선형 결합이다.

aₙ = c₀·2ⁿ + c₁·(−1)ⁿ
a₀ = 0 → c₀ + c₁ = 0,   a₁ = 1 → 2c₀ − c₁ = 1   →   c₀ = 1/3, c₁ = −1/3

같은 결과가 나온다. 생성함수의 분모 1 − x − 2x²를 인수분해한 (1 − 2x)(1 + x)에 나온 2와 −1이 바로 특성근이다. 중근 r이 있으면 그 항은 (c + d·n)·rⁿ 꼴이 된다.

방법 3: 행렬 거듭제곱과 대각화

점화식을 벡터의 선형 변환으로 쓸 수 있다.

[aₙ  ]   [1 2] [aₙ₋₁]                [aₙ  ]   [1 2]ⁿ⁻¹ [1]
[aₙ₋₁] = [1 0] [aₙ₋₂]   이므로       [aₙ₋₁] = [1 0]     [0]

행렬 T의 거듭제곱은 그대로 계산하기 어렵지만, 대각 행렬의 거듭제곱은 대각 원소만 거듭제곱하면 된다. 그래서 T를 대각화한다.

T·v = λ·v를 만족하는 고유값 λ와 고유벡터 v를 찾는다. 0이 아닌 v가 있으려면 T − λI가 역행렬을 갖지 않아야 하므로 det(T − λI) = 0.
det [[1−λ, 2], [1, −λ]] = λ² − λ − 2 = 0 → λ = 2, −1. 특성방정식과 똑같다.
고유벡터 (2, 1), (1, −1)을 열로 하는 행렬 B로 T = B·D·B⁻¹, D = diag(2, −1)로 쓴다.
Tⁿ⁻¹ = B·Dⁿ⁻¹·B⁻¹이므로 계산하면 다시 aₙ = (2ⁿ − (−1)ⁿ)/3이 나온다.

즉 세 방법은 모두 변환의 고유값을 찾는 같은 일을 다른 언어로 한다. 특성방정식은 동반 행렬(companion matrix)의 고유값 방정식이고, 생성함수의 분모는 그 다항식을 뒤집은 것이다.

알고리즘에서 쓰는 법

상황	방법
증가 속도·복잡도만 알고 싶다	특성근 중 절댓값이 가장 큰 것 r → Θ(rⁿ) (피보나치는 황금비 ≈ 1.618)
n이 매우 크고 답을 정수(mod M)로 출력	일반항 대신 행렬 거듭제곱을 분할 정복으로 계산: O(k³ log n)
일반항에 무리수가 나온다	부동소수점 오차가 크므로 정수 행렬 거듭제곱을 쓴다
작은 n	그냥 반복문 O(n)

def mat_mul(A, B, mod):
    return [[sum(A[i][k] * B[k][j] for k in range(len(B))) % mod
             for j in range(len(B[0]))] for i in range(len(A))]
 
def mat_pow(M, n, mod):
    R = [[int(i == j) for j in range(len(M))] for i in range(len(M))]
    while n:
        if n & 1:
            R = mat_mul(R, M, mod)
        M = mat_mul(M, M, mod)
        n >>= 1
    return R
 
def jacobsthal(n, mod=10**9 + 7):
    if n == 0:
        return 0
    return mat_pow([[1, 2], [1, 0]], n - 1, mod)[0][0]   # [a₁, a₀] = [1, 0]
 
print([jacobsthal(i) for i in range(9)])  # [0, 1, 1, 3, 5, 11, 21, 43, 85]

분할 정복 점화식(T(n) = a·T(n/b) + f(n))은 이 노트의 대상이 아니다. 그런 점화식은 전개하거나 마스터 정리로 푼다(분할 정복의 점화식).

정리

상수 계수 선형 점화식의 일반항은 특성근의 거듭제곱의 선형 결합이다.
생성함수(부분분수), 특성방정식, 행렬 대각화는 모두 같은 고유값을 찾는다.
야콥스탈 수열: aₙ = aₙ₋₁ + 2aₙ₋₂ → (2ⁿ − (−1)ⁿ)/3
프로그래밍에서는 큰 n에 행렬 거듭제곱 O(log n)을 쓰고, 일반항은 복잡도 분석에 쓴다.

버그 제보