84 세지 않고 센다
— 생성함수
84.1 셈의 한계
조합론은 센다. 몇 가지 경우가 있는가. 몇 가지 방법이 있는가.
피보나치 수열: \(F(0) = 0\), \(F(1) = 1\), \(F(n) = F(n-1) + F(n-2)\).
규칙은 단순하다. 앞의 둘을 더하면 된다. 0, 1, 1, 2, 3, 5, 8, 13, 21, … 모든 항이 정수고, 모든 연산이 덧셈이다. 비합리적인 것은 아무것도 없다.
그런데 \(F(100)\)은? 앞의 99항을 전부 계산해야 한다. \(F(n)\)의 일반항은? 직접 세는 방법으로는 점화식 너머를 볼 수 없다.
84.2 허구의 변수
수열 전체를 하나의 식에 포장한다.
\[F(x) = F_0 + F_1 x + F_2 x^2 + F_3 x^3 + \cdots\]
\(x\)에 값을 넣지 않는다. \(x = 3\)일 때 \(F(3)\)이 얼마인지 묻지 않는다. \(x\)는 변수가 아니라 자리 표시자(formal variable)다. 의미 없는 기호. \(F(x)\)는 여기서 함수값을 계산하는 대상이 아니라 형식적 멱급수(formal power series) — 수열의 대수적 포장 — 로 다룬다.
그런데 이 포장에 대수학이 작동한다.
점화식 \(F(n) = F(n-1) + F(n-2)\)를 \(F(x)\)의 언어로 번역하면:
\[F(x) = x F(x) + x^2 F(x) + x\]
정리하면:
\[F(x) = \frac{x}{1 - x - x^2}\]
무한히 계속되는 점화식이 분수 하나가 되었다. 무한이 유한으로 접혔다.
84.3 황금비
분모 \(1 - x - x^2\)를 인수분해하면 \(-(x - 1/\varphi)(x - 1/\psi)\)이 되고, \(F(x)\)를 두 분수의 합으로 쪼갤 수 있다(부분분수 분해). 각 분수를 급수로 전개하면 \(x^n\)의 계수가 바로 \(F_n\)이 된다:
\[F_n = \frac{1}{\sqrt{5}}\left(\varphi^n - \psi^n\right), \quad \varphi = \frac{1+\sqrt{5}}{2}, \quad \psi = \frac{1-\sqrt{5}}{2}\]
멈추고 본다.
수열의 모든 항은 정수다. 모든 연산은 덧셈이다. 무리수는 어디에도 없었다. 그런데 일반항에 \(\sqrt{5}\)와 황금비 \(\varphi\)가 들어 있다.
\(\sqrt{5}\)는 수열 안에 없었다. 수열의 구조 안에 있었다. 점화식 \(F(n) = F(n-1) + F(n-2)\)의 특성방정식 \(1 - x - x^2 = 0\)이 무리수 근을 가지고 있었고, 생성함수의 대수적 분해가 그것을 꺼낸 것이다.
직접 세면 보이지 않는다. 0, 1, 1, 2, 3, 5, 8, 13 — 정수만 보인다. 값을 넣지 않는 변수 \(x\)를 도입하고, 의미 없는 기호에 대수학을 적용한 순간, 정수 수열 안에 숨어 있던 무리수가 나타난다.
84.4 맺음
생성함수가 아름다운 이유는 답을 빨리 구해서가 아니다.
세지 않고 센다. 의미 없는 변수를 도입하면, 정수의 수열에서 황금비가 나온다.
84.5 관련 문서
- 갈루아와 5차방정식 — 갈루아는 근의 구조를 봤고, 생성함수는 수열의 구조를 본다
- 라그랑지안 — 뉴턴은 한 걸음씩 봤고, 라그랑주는 경로 전체를 봤다. 점화식은 한 항씩 보고, 생성함수는 수열 전체를 본다
- 보이지 않던 인수 — 가우스 정수는 좌표를 넓혀 숨은 인수를 드러냈고, 생성함수는 허구의 변수로 숨은 구조를 드러낸다
- 증명은 언제 아름다운가 — 형식의 아름다움이 내용을 결정하는 순간