점화식·생성함수

이전 값으로 다음 값을 만들기

점화식은 초기 조건과 갱신 규칙을 함께 지정합니다. 규칙만으로는 수열이 정해지지 않습니다. 이 실습은 a₀=0,a₁=1과 aₙ=paₙ₋₁+qaₙ₋₂를 사용합니다. p=q=1이면 0,1,1,2,3,5,8,13,21,…입니다. n=8의 값은 21입니다.

동적 계획법은 작은 하위 문제의 답을 저장하고 이 규칙으로 더 큰 문제의 답을 구합니다. 점화식의 n은 문제 크기나 단계 수이고 반드시 물리적 시간은 아닙니다.

생성함수는 계수를 담는 그릇

수열을 형식적 멱급수 G(x)=Σₙ₌₀∞aₙxⁿ에 저장합니다. 여기서 x는 먼저 실제 숫자가 아니라 계수를 정렬하는 기호입니다. 계수별 유한 연산으로 등식을 읽는 형식적 급수 단계에서는 수렴을 아직 가정하지 않습니다.

왼쪽에서 a₀와 a₁x를 떼면 n≥2 항만 남습니다. 오른쪽의 xG와 x²G는 이전 항의 인덱스를 맞춥니다. 분모의 상수항이 1이므로 형식적 역급수가 존재합니다. 이 유도는 초깃값에 의존하며 a₀를 바꾸면 분자도 달라집니다.

실수 x를 대입할 때의 추가 조건

형식적 등식에 숫자를 넣어 무한합으로 해석하려면 수렴을 확인해야 합니다. p,q≥0이고 둘 다 0이 아닐 때 지배 성장률은 ρ=(p+√(p²+4q))/2이고 수렴 반지름은 R=1/ρ입니다. 이 예제의 초기 조건에서는 해당 지배 성분이 사라지지 않습니다.

p=q=1이면 ρ=φ≈1.618, R≈0.618입니다. 따라서 x=0.5는 수렴 구간 안이고 G(0.5)=2입니다. N=8 부분합은 0부터 8까지의 항만 합하므로 1.65234375입니다. N을 늘려 무한합에 접근하는 것을 보되 유한 표만으로 일반 수렴을 증명했다고 해석하지 마세요.

반대로 x=0.8에서 유리식은 −20/11≈−1.818입니다. 그런데 급수의 항들은 음수가 아니며 0으로 가지도 않습니다. 급수는 발산하고 이 음수 값과 같지 않습니다. 유리식의 연장값과 원래 급수의 합은 다른 개념입니다.

경계와 특수한 경우

실습의 수렴 판정은 |x|<R인 내부를 사용합니다. 이 비음수 계수 계열의 비다항식 경우에는 |x|=R에서 일반항이 0으로 가지 않아 수렴하지 않습니다. 다른 멱급수의 경계 거동을 이 사례에서 일반화하지 마세요.

p=q=0이면 a₁만 비영인 다항식 G=x입니다. 수렴 반지름에 제한이 없으며 화면에서는 유한 수치 R 대신 —와 설명을 제공합니다. 유리식의 분모가 0이면 그 값도 —입니다. N=0에서는 a₀=0과 부분합 0이 정상 결과입니다.

표와 계산 절차

그림은 aₙ의 성장이고 표의 세 번째 열은 x를 대입한 항 aₙxⁿ입니다. 두 양은 다릅니다. 실습은 N≤12인 작은 정수 계수를 점화식으로 직접 계산합니다. 작은 정수 모형의 정확성이 임의로 큰 n에서의 부동소수점 계산을 보장하지는 않습니다.

다음 절차로 독립 검산할 수 있습니다.

p, q, x, N = 1, 1, 0.5, 8
values = [0, 1]
for n in range(2, N + 1):
    values.append(p * values[-1] + q * values[-2])
partial = sum(values[n] * x**n for n in range(N + 1))
print(values[N], partial)  # 21, 1.65234375

AI와 연구에서의 역할

구조 개수, 탐색 비용, 토큰 문법의 조합 계수를 점화식으로 나타낼 수 있습니다. 모델의 은닉 상태 갱신도 점화식이지만 비선형 벡터 함수라면 이 스칼라 선형 생성함수 해법을 그대로 적용할 수 없습니다. 선형성·초깃값·계수의 시간 의존 여부를 확인하세요.

확인 문제와 답

1. p=1,q=0이면 수열은? **0,1,1,1,…이고 G=x/(1−x)**입니다.
2. p=q=1,N=3이면 부분합은? x+x²+2x³입니다.
3. x=0.8에서 유리식이 유한하다는 사실이 무엇을 보장하나요? 그 식의 대입값만 보장하며 급수 수렴을 보장하지 않습니다.

추가 읽기: MIT Mathematics for Computer Science. 유도와 계산은 본문에 명시한 초기 조건에 한정합니다.