이산미적분학

구간에서 정의된 함수가 있을 때 미분은 구간의 특정한 점에서 함수의 변화율을 재고, 적분은 그 변화를 쌓아 넓이나 총량을 구한다. 이 모든 것의 바탕에는 극한이 있다. 함수 \(f\)의 도함수는 \[ f'(x)=\lim_{h\to 0}\frac{f(x+h)-f(x)}{h} \] 로 정의되는데, 보다시피 간격 \(h\)를 \(0\)에 한없이 가깝게 하는 극한이 핵심이다. 이와 같은 극한을 사용할 수 있는 이유는 함수 \(f\)가 구간에서 정의되었기 때문이다. 여기서 구간은 수를 나타내는 점이 연속적으로 이어져 있는 선분이라고 생각할 수 있다.

그런데 우리가 실제로 다루는 것 중에는 뚝뚝 끊긴 것이 많다. 수열 \(a_1,\, a_2,\, a_3,\, \dots\)은 항에서 항으로 건너뛸 뿐 그 ‘사이’가 없다. 은행 이자는 매달 한 번씩 붙고, 알고리즘의 연산 횟수는 한 단계씩 늘어난다. 이런 대상에는 극한으로 정의한 미분이 잘 들어맞지 않는다. 애초에 ‘아주 가까운 점’이라는 게 없기 때문이다.

그래서 과감하게 이런 생각을 해보자. 극한이 없으면 어떨까? \(h\)를 \(0\)으로 보내는 대신, 자연스러운 최소 간격인 \(1\)로 고정시키는 것이다. 그러고도 미분과 적분에 대응하는 ‘미적분’을, 곧 차이와 합의 이론을 다질 수 있을까? 놀랍게도 그것이 가능하고, 그와 같은 과정을 통해 얻은 결과가 원래의 미적분과 잘 대응된다. 즉 연속 세계에서 살펴본 미적분과 관련된 다양한 정리가 이산 세계에 쌍둥이를 두고 있다. 덤으로, 수학적 귀납법이나 식의 변형을 통해 확인하였던 수열의 합 \[1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}\] 과 같은 공식을, 이 이산미적분에서는 적분하듯 유도해 낸다.

차분: 극한을 버린 미분

미분의 정의를 다시 생각해 보자. 함수 \(f\)의 도함수는 차이 \(f(x+h)-f(x)\)를 \(h\)로 나눈 뒤 \(h\to 0\)인 극한을 취한 것이다. 이산미적분의 출발점은 단순하다. 극한을 취하지 않는다. \(h\)를 \(1\)로 고정시키고 차이 그 자체만 본다. 이렇게 정의한 연산을 차분(difference)이라고 부르고, 기호로 \(\Delta\)로 나타낸다. 즉 \[ \Delta f(x)=f(x+1)-f(x) \] 이다. 이것이 미분의 이산 버전이다.¹

연속 세계의 미분과 달리 이산 세계에는 극한이 없다. 그래서 \(f\)가 연속일 필요도, 매끄러울 필요도 없다. 정수에서만 정의된 수열이어도 차분이 온전하게 정의된다. 몇 가지 계산의 예를 살펴보자. 상수함수의 차분은 \(0\)이다. 일차함수 \(f(x)=ax+b\)의 차분은 \[ \Delta(ax+b)=a(x+1)+b-(ax+b)=a \] 로서 기울기 \(a\)가 그대로 나온다. 여기까지는 연속 세계의 미분과 똑같다. 그런데 \(x^2\)을 차분하면 알고 있던 식과 달라진다. \[ \Delta(x^2)=(x+1)^2-x^2=2x+1 \] 연속 세계의 도함수라면 \(2x\)가 나올 텐데, 차분에서는 \(+1\)이 붙는다. 이 사소해 보이는 차이가, 사실은 이산 세계에서 \(x^2\)이 ‘자연스러운 대상’이 아니라는 첫 신호다. (하지만 다음 절에서는 이 결과가 자연스러워지도록 거듭제곱을 다시 정의하는 방법을 살펴볼 것이다.)

미분을 두 번 하듯 차분도 두 번 할 수 있다. 즉 \(\Delta^2 f=\Delta(\Delta f)\)는 이계도함수에 대응한다. 예컨대 \[ \Delta^2(x^2)=\Delta(2x+1)=2 \] 인데, 이것은 미분 \[\frac{d^2}{dx^2}x^2=2\] 에 대응된다. 일반적으로 \(n\)차 다항식은 \(n\)번 차분하면 상수가 되고 \(n+1\)번 차분하면 \(0\)이 된다. 이것은 다항식을 미분할 때 도함수의 성질과 일치한다. 또한 차분은 미분처럼 선형이다. 즉 \(\Delta(af+bg)=a\,\Delta f+b\,\Delta g\)가 성립한다.

차분과 관련된 도구를 하나 더 소개한다. 함수의 자리를 한 칸 옮기는 이동연산자(shift operator) \(\mathrm{E}\)를 \(\mathrm{E}f(x)=f(x+1)\)로 정의하면, 차분은 \(\Delta=\mathrm{E}-\mathrm{I}\)로 깔끔하게 쓸 수 있다. (여기서 \(\mathrm{I}\)는 항등 연산자이다.) 지금은 사소해 보이지만, 이 \(\mathrm{E}\)가 글 마지막에 두 미적분을 잇는 다리에서 결정적인 역할을 한다. 그리고 차분을 표로 만들어 두면 쓸모가 많다. 수열을 한 줄 적고 그 아래에 이웃한 항들의 차분을, 또 그 아래에 차분의 차분을 적어 내려가는 식이다. 차분표에서 어떤 차분열이 계속 상수로 유지된다면, 그 수열은 정수점에서 다항식으로 주어졌다고 볼 수 있다. (다만 유한 개의 항만 놓고 만든 차분표에서는 “다항식일 것 같다”는 추정일 뿐, 수열 전체가 다항식임을 증명하는 것은 아니다.) 이 ‘차분표’가 어떻게 수열을 예측하게 해 주는지는 뉴턴의 공식을 다루는 절에서 다시 보자.

하강 거듭제곱: 이산 세계의 진짜 거듭제곱

앞 절에서 \(\Delta(x^2)=2x+1\)이라는 결과를 봤다. 연속 세계의 미적분에서 모든 계산의 기본은 다음과 같은 거듭제곱 법칙이다. \[\dfrac{d}{dx}x^n=n\,x^{n-1}\] 짧고 깔끔하다. 이산 세계에서도 차분에 대해 같은 법칙이 성립하면 유용할 것이다. 이것을 위해서는 보통의 거듭제곱 \[x^n=x\cdot x\cdots x\] 대신, 곱하는 인수를 하나씩 줄여 가며 곱하는 방법을 사용해야 한다. 즉 \(n\)이 자연수일 때, 하강 거듭제곱(falling factorial)을 다음과 같이 정의한다.² \[ x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1) \] 오른쪽은 \(x\)부터 시작해 \(1\)씩 줄여 가며 곱한 \(n\)개의 인수이다. 특히 \(x^{\underline 0}=1\)로 약속한다.

하강 거듭제곱을 몇 개 적어 보면 다음과 같다. \[\begin{aligned} x^{\underline 1} & = x ,\\ x^{\underline 2} & = x(x-1)=x^2-x,\\ x^{\underline 3} & = x(x-1)(x-2) \end{aligned}\] 거듭제곱과 달리, \(1\)씩 빼면서 곱하는 것이 핵심이다. 이제 이 하강 거듭제곱을 차분해 보자.

이산거듭제곱 법칙. 모든 자연수 \(n\)에 대하여 \[ \Delta\bigl(x^{\underline{n}}\bigr)=n\,x^{\underline{n-1}} \] 이 성립한다.

증명은 인수를 잘 묶기만 하면 된다. \((x+1)^{\underline{n}}\)과 \(x^{\underline{n}}\)을 각각 풀어 쓰면 \[\begin{aligned} (x+1)^{\underline{n}} &= (x+1)\cdot x(x-1)\cdots(x-n+2),\\[6pt] x^{\underline{n}} &= x(x-1)\cdots(x-n+2)\cdot(x-n+1) \end{aligned}\] 인데, 가운데 \(x(x-1)\cdots(x-n+2)\)는 정확히 \(x^{\underline{n-1}}\)이다. (즉 인수가 \(n-1\)개이다.) 두 식이 이 공통인수를 가지므로 \[ \Delta\bigl(x^{\underline{n}}\bigr)=(x+1)^{\underline n}-x^{\underline n}=x^{\underline{n-1}}\bigl[(x+1)-(x-n+1)\bigr]=n\,x^{\underline{n-1}} \] 이다. 보다시피 우리가 알던 공식 \[\frac{d}{dx}x^n=n x^{n-1}\] 과 똑같다. 하강 거듭제곱을 차분하는 것은 보통의 단항식을 미분하는 것과 같다. 즉 하강 거듭제곱이 이산미적분의 ‘진짜 거듭제곱’인 셈이다.

이 법칙은 음의 지수까지 자연스럽게 확장된다. \(n>0\)일 때 \[ x^{\underline{-n}}=\frac{1}{(x+1)(x+2)\cdots(x+n)} \] 로 정의하면, 위 법칙 \(\Delta(x^{\underline n})=n x^{\underline{n-1}}\)이 모든 정수 \(n\)에서 성립한다. 가령 \(n=-1\)이면 \[x^{\underline{-1}}=\dfrac{1}{x+1}\] 이고, \[ \Delta\Bigl(\frac{1}{x+1}\Bigr)=\frac{1}{x+2}-\frac{1}{x+1}=\frac{-1}{(x+1)(x+2)}=(-1)\,x^{\underline{-2}} \] 로서 우리가 알던 미분 공식과 같다.

마지막으로, 보통 거듭제곱과 하강 거듭제곱을 서로 변환할 수 있다면, 어떤 다항식이든 차분을 다룰 수 있을 것이다. 몇 가지 경우를 살펴보면 \[ x^2=x^{\underline 2}+x^{\underline 1},\quad x^3=x^{\underline 3}+3x^{\underline 2}+x^{\underline 1} \] 이다. 여기서 등장하는 계수 \(1,\,1\)과 \(1,\,3,\,1\)은 제2종 스털링 수다. 반대로 하강 거듭제곱을 보통 거듭제곱으로 풀어 쓸 때는 제1종 스털링 수가 등장한다.

합: 차분의 역연산, 그리고 기본정리

연속 세계의 미적분에서 적분은 미분의 역연산이고, 미적분의 기본정리가 정적분과 부정적분을 이어 준다. 이 구조를 이산 세계에 그대로 옮겨 보자.

차분을 거꾸로 환원시키는 연산을 생각하자. 어떤 함수 \(F\)가 \(\Delta F=f\)를 만족시키면, \(F\)를 \(f\)의 부정합(indefinite sum)이라 부르고 \[ \sum f(x)\,\delta x=F(x)+C \] 로 나타낸다.³ 여기서 \(\delta x\)는 적분의 \(dx\)에 대응하는 이산 기호다. 부정합은 부정적분의 이산 버전이다.

앞 절의 거듭제곱 법칙을 거꾸로 읽으면, 곧바로 부정합 공식이 나온다. \[ \sum x^{\underline{n}}\,\delta x=\frac{x^{\underline{n+1}}}{n+1}+C\quad(n\neq -1) \] 이 식은 다음과 같은 부정적분 공식과 닮았다. \[\int x^n\,dx=\frac{x^{n+1}}{n+1}\] 그리고 적분과 마찬가지로, 부정합에서 단 하나의 예외가 \(n=-1\)인 경우이다.

연속 세계의 미적분에서 \[\int x^{-1}\,dx=\ln x\] 는 \(x^n\) 형태의 함수 중 거듭제곱 법을 사용하여 적분할 수 없는 유일한 형태이다. 이산 세계에서는 무엇이 \(x^{\underline{-1}}=\frac{1}{x+1}\)의 부정합일까? 바로 조화수(harmonic number)를 떠올릴 수 있다. 즉 \(H_0 = 0\)이라고 두고, 양의 정수 \(x\)에 대하여 \[H_x=1+\frac{1}{2}+\cdots+\frac{1}{x}\] 라고 두자. 그러면 이 함수의 차분은 \[ \Delta H_x=H_{x+1}-H_x=\frac{1}{x+1} \] 이므로, \[\sum x^{\underline{-1}}\,\delta x=H_x+C\] 이다. 조화수가 바로 이산 세계의 로그인 셈이다.⁴ 두 세계 모두에서 거듭제곱 법칙이 깨지는 단 한 곳이 정확히 ‘로그’라는 점이 재미있다.

이제 정적분에 해당하는 정합을 정의한다. \(a < b\)인 정수 \(a,\) \(b\)에 대하여 \[ \sum_{a}^{b} f(x)\,\delta x:=\sum_{k=a}^{b-1}f(k) \] 로 정의한다. 합의 범위가 \(a\)부터 \(b-1\)까지, 즉 위끝을 포함하지 않는다는 점에 주의하자. (반열린구간 \([a,b)\)를 사용하는 약속이 처음에는 낯설지만, 바로 다음에 나오는 기본정리를 완벽하게 깔끔하게 만들어 준다. 정적분 \(\int_a^b\)이 ‘\(b\) 너머’를 포함하지 않는 것과도 통한다. 『구체 수학』도 정확히 이 약속을 쓴다.)

이산미적분의 기본정리. \(\Delta F=f\)이면 \[ \sum_{a}^{b} f(x)\,\delta x=F(b)-F(a) \] 이다.

증명은 한 줄이면 충분하다. 합을 구하면 가운데 항들이 모두 상쇄되어 사라진다. \[ \sum_{k=a}^{b-1}f(k)=\sum_{k=a}^{b-1}\bigl[F(k+1)-F(k)\bigr]=F(b)-F(a) \] 이것은 미적분학의 기본정리인 \[\int_a^b f(x)\,dx=F(b)-F(a)\] 와 닮았다. 위 정리를 실제로 사용할 때 어려운 부분은 부정합 \(F\)를 찾는 일인데, 이것은 미적분학의 기본정리를 사용하여 적분을 계산할 때 부정적분을 찾는 일이 어려운 것과 똑같다.

이제 거듭제곱의 합을 ‘적분하듯’ 구해 보자. 먼저 \(1+2+\cdots+n\)을 구해 보자. \(x=x^{\underline 1}\)이므로 부정합은 \(\frac{x^{\underline 2}}{2}\)이다. 따라서 \[ \sum_{0}^{\,n+1} x\,\delta x=\left[\frac{x^{\underline 2}}{2}\right]_{0}^{n+1}=\frac{(n+1)^{\underline 2}}{2}=\frac{(n+1)n}{2} \] 이다. (아래끝 \(0\)은 \(0^{\underline 2}=0\)이므로 사라진다.) 여기서 좌변이 \(0+1+\cdots+n\)이므로 바로 \[ 1+2+\cdots+n=\frac{n(n+1)}{2} \] 이 나온다.

이번엔 제곱의 합을 구해 보자. 앞 절에서 \(x^2=x^{\underline 2}+x^{\underline 1}\)이었으니, 부정합은 항별로 \[ \sum x^2\,\delta x=\frac{x^{\underline 3}}{3}+\frac{x^{\underline 2}}{2}+C \] 이다. 이를 \(0\)부터 \(n+1\)까지 정합하면 \[ \sum_{k=1}^{n}k^2=\left[\frac{x^{\underline 3}}{3}+\frac{x^{\underline 2}}{2}\right]_{0}^{n+1}=\frac{(n+1)n(n-1)}{3}+\frac{(n+1)n}{2}=\frac{n(n+1)(2n+1)}{6} \] 이다. 우리가 잘 알고 있는 공식과 일치한다.

이 방법은 다른 거듭제곱의 합에도 사용할 수 있다. \(p\)가 자연수일 때 \(\sum k^p\)을 구하려면, \(x^p\)을 하강 거듭제곱으로 표현하고(스털링 수를 사용한다), 항별로 부정합한 뒤, 정합하면 된다. 결과는 언제나 \(n\)에 대한 \((p+1)\)차 다항식이 된다. 이 공식을 파울하버 공식(Faulhaber’s formula)이라고 부른다.⁵ 중요한 점은, 우리가 공부했던 합 공식들이 개별적으로 존재하는 공식이 아니라, 하나의 원리를 통해 얻어낼 수 있는 관계를 가지고 있다는 점이다.

부분합: 이산 세계에서의 부분적분

연속 세계의 미적분에서 사용하는 다음과 같은 부분적분 공식을 생각해 보자. \[\int u\,dv=uv-\int v\,du\] 이 공식의 이산 버전도 똑같은 방식으로 얻을 수 있다. 출발점은 차분의 곱셈 법칙이다. 두 함수의 곱을 차분하면, 항을 더했다 빼는 방법을 통해 \[ \Delta(uv)=u\,\Delta v+(\mathrm{E}v)\,\Delta u \] 를 얻는다. 여기서 \(\mathrm{E}v(x)=v(x+1)\)이다. 구체적으로 계산해 보면 \[\begin{aligned} \Delta(uv) & = u(x+1)v(x+1)-u(x)v(x) \\[6pt] &=v(x+1)\bigl[u(x+1)-u(x)\bigr]+u(x)\bigl[v(x+1)-v(x)\bigr] \end{aligned}\] 이고, 마지막 식이 \((\mathrm{E}v)\Delta u+u\,\Delta v\)이다. 미분의 곱셈 법칙 \((uv)'=u'v+uv'\)과 거의 같되, 한쪽 인수에 자리이동 \(\mathrm{E}\)가 한 번 끼어든다는 점만 다르다.⁶

양변을 부정합하면(즉 \(\Delta\)의 역을 취하면) \(\sum\Delta(uv)\,\delta x=uv\)이므로 \[ \sum u\,\Delta v\,\delta x=uv-\sum (\mathrm{E}v)\,\Delta u\,\delta x \] 가 된다. 이것이 부분합(summation by parts)이다. 정합 형태로는 \[ \sum_{a}^{b} u\,\Delta v\,\delta x=\bigl[uv\bigr]_{a}^{b}-\sum_{a}^{b}(\mathrm{E}v)\,\Delta u\,\delta x \] 이다. 부분적분에서 자리이동 \(\mathrm{E}\) 하나가 추가된 꼴이다.

이 공식을 활용하여 다음 합을 구해 보자. \[\displaystyle\sum_{k=0}^{n-1}k\,2^k\] 이 합은 적분 \[\int x e^x\,dx\]의 이산 세계 버전이다. \(u=x\), \(\Delta v=2^x\)으로 놓는다. 그러면 \(\Delta u=1\)이고, \(2^x\)의 부정합은 \(2^x\) 자신이다. (\(\Delta 2^x=2^{x+1}-2^x=2^x\)이기 때문이다.) 또한 \(\mathrm{E}v=2^{x+1}=2\cdot 2^x\)이다. 여기서 부분합 공식을 활용하면 다음을 얻는다. \[\begin{aligned} \sum x\,2^x\,\delta x &= x\,2^x-\sum 2\cdot 2^x\,\delta x\\[6pt] & =x\,2^x-2\cdot 2^x+C \\[6pt] & =(x-2)\,2^x+C \end{aligned}\] 얻은 결과를 정합하면 \[ \sum_{k=0}^{n-1}k\,2^k=\bigl[(x-2)2^x\bigr]_{0}^{n}=(n-2)2^n+2 \] 가 된다. \(n=3\)을 넣어 보면 \(0\cdot1+1\cdot2+2\cdot4=10\)이고, 공식도 \((3-2)2^3+2=10\)으로 맞는다. 이 결과는 \[\int x e^x\,dx=(x-1)e^x\] 의 이산 세계 버전이라 할 만하다. 덧붙이면, 이 부분합은 해석학에서 ‘아벨의 합 공식(Abel summation)’이라는 이름으로 따로 알려져 있고, 디리클레 급수를 포함하여 다양한 급수의 수렴 판정에 사용된다.⁷ 부분적분을 떠올리면, 왜 이 도구가 그렇게 자주 등장하는지 짐작이 갈 것이다.

이산지수함수와 뉴턴의 차분 공식

앞 절에서 \(2^x\)의 차분이 자기 자신이 된다는 사실을 사용하였다. 이것은 그냥 지나치기 아까운 성질이다. 연속 세계의 미적분에서 \(e^x\)는 미분한 결과가 자기 자신인 함수로서, 모든 지수함수와 로그함수의 기준점이다. 이산 세계에서 그 역할은 누가 맡을까? 일반적으로 \[\Delta(c^x)=c^{x+1}-c^x=(c-1)c^x\]이므로, \(c^x\)은 차분 \(\Delta\)의 고유함수이고 그 고윳값은 \(c-1\)이다. 고윳값이 정확히 \(1\)이 되는 밑은 \(c-1=1\), 즉 \(c=2\)다. 그래서 \[ \Delta(2^x)=2^x \] 이고, \(2^x\)이 이산 세계의 \(e^x\) 역할을 한다.⁸ \(e\)가 ‘변화율이 곧 값’인 밑이라면, \(2\)는 ‘차분이 곧 값’인 밑인 셈이다.

여기서 한 걸음 더 나가면 테일러 정리의 이산 버전까지 생각할 수 있다. 테일러 정리를 사용하면 해석적인 함수 \(f\)를 \[ f(x)=\sum_{k=0}^{\infty}\frac{f^{(k)}(0)}{k!}\,x^k \] 와 같은 꼴로 나타낼 수 있다. 이산 세계에서는 다항식에 대한 뉴턴의 전진차분 공식(Newton’s forward difference formula)이 있다. \[ f(x)=\sum_{k=0}^{\infty}\Delta^k f(0)\,\binom{x}{k},\quad \binom{x}{k}=\frac{x^{\underline{k}}}{k!} \] 이 식은 \(f\)가 임의의 수열일 때 \(0\) 이상인 정수 \(n\)에 대하여 다음과 같이 바뀐다. \[f(n) = \sum_{k=0}^{n} \binom{n}{k} \Delta ^k f(0)\] 테일러 정리와 전진차분 공식을 나란히 두고 비교해 보면 닮은 점이 보인다. 미분 \(\frac{d}{dx}\)는 차분 \(\Delta\)로, 단항식 \(x^k\)은 하강 거듭제곱 \(x^{\underline k}\)으로, 따라서 단항식 \(\frac{x^k}{k!}\)은 이항계수 \(\binom{x}{k}=\frac{x^{\underline k}}{k!}\)으로, 그리고 \(k\)계도함수의 값 \(f^{(k)}(0)\)은 \(k\)계차분의 값 \(\Delta^k f(0)\)으로 바뀐다.

게다가 다항식에 대해서는 이 합이 유한합이라 수렴을 걱정할 필요조차 없다. \(f(x)=x^2\)에 이 공식을 적용해 보자. \(f(0)=0\), \(\Delta f(0)=1\)(\(\Delta f=2x+1\)이므로), \(\Delta^2 f(0)=2\)이고 그 이후의 차분은 모두 \(0\)이다. 이 결과를 전진차분 공식에 넣으면 \[ f(x)=0\cdot\binom{x}{0}+1\cdot\binom{x}{1}+2\cdot\binom{x}{2}=x+x(x-1)=x^2 \] 으로서, 처음 함수가 다시 나온다.

이 공식은 차분표의 유용성을 보여준다. 어떤 다항식 수열의 차분표를 그리면, 맨 위 대각선에 놓이는 값들이 바로 \(\Delta^0 f(0),\) \(\Delta^1 f(0),\) \(\Delta^2 f(0),\) \(\dots\)이다. 전진차분 공식은 이 몇 개의 수만으로 수열 전체를 복원하고, 그 다음 항이 무엇일지 예측하게 해 준다. 이것이 유한차분 보간법(뉴턴–그레고리 보간)의 원리이다. 이 원리는 옛날에 수표(數表)를 만들고 메우는 데 쓰였으며 지금도 수치해석에서 활용되고 있다.⁹ 한마디로, 수열이 \(d\)차 다항식이라는 것, \(\Delta^{d+1} f=0\)이라는 것, 그리고 뉴턴 전개에서 \(0\)이 아닌 계수 \(\Delta ^{k} f(0)\)이 유한 개뿐이라는 것은 같은 구조를 나타낸다.

두 미적분을 잇는 다리: 오일러–매클로린 공식

지금까지 본 것은 이산미적분이 연속 세계의 미적분을 ‘닮았다’는 이야기였다. 그런데 둘은 그저 닮은꼴에 그치지 않고, 실제로 한 줄로 연결되어 있다. 그 다리가 오일러–매클로린 공식이다.

합 \(\sum f(k)\)와 적분 \(\int f(x)\,dx\)는 둘 다 \(f\)의 값을 ‘쌓는’ 연산이다. \(f\)가 천천히 변하면 둘은 거의 같을 것이다. 합은 적분을 폭이 \(1\)인 직사각형들로 근사한 것이나 마찬가지이기 때문이다. 오일러–매클로린 공식은 이 ‘거의 같다’를 정확한 등식으로 바꿔, 합과 적분의 차이가 정확히 무엇인지 알려 준다.

충분히 매끄러운 함수 \(f\)와 \(a < b\)인 정수 \(a,\) \(b\)에 대하여 \[ \sum_{k=a}^{b}f(k)=\int_{a}^{b}f(x)\,dx+\frac{f(a)+f(b)}{2}+\sum_{j=1}^{m} \frac{B_{2j}}{(2j)!}\Bigl[f^{(2j-1)}(b)-f^{(2j-1)}(a)\Bigr]+R_m \] 이 성립한다. 보통 \(m\)을 적당히 정하여 유한 개의 보정항만 쓰며, \(R_m\)을 따로 추정한다. 이 급수는 일반적으로 수렴급수가 아니라 점근전개로 이해해야 한다. 또한 위 공식에서 좌변의 합은 보통합, 즉 위끝 \(b\)를 포함하는 합을 나타낸다. (이 공식은 오일러와 매클로린이 1730년대에 각자 발견했다.) 여기서 \(B_{2j}\)가 베르누이 수이다. 즉 \[B_2=\tfrac16,\ B_4=-\tfrac1{30},\ B_6=\tfrac1{42},\dots .\] 위 공식을 더 깊게 살펴보자. 맨 앞의 적분항에 끝점 보정 \(\frac{f(a)+f(b)}{2}\)를 더한 것은 사다리꼴 공식(trapezoidal rule)과 같은 ‘끝점 반가중’ 구조를 가진다. 그러니까 오일러–매클로린 공식은 ‘사다리꼴 공식 + 베르누이 수로 짜인 보정식’인 셈이다. 매끄러운 주기함수에서 사다리꼴 적분이 유난히 잘 맞는 이유도 여기 있다. 보정항들이 양 끝에서 상쇄되어 사라지기 때문이다.

그리고 이 식이, 우리가 \(\sum k^p\)에서 만났던 베르누이 수의 정체를 밝혀 준다. 베르누이 수는 합과 적분 사이를 연결하는 상수다. 야코프 베르누이가 거듭제곱의 합을 구하다 발견한 그 수가, 합과 적분을 잇는 다리의 받침돌로 다시 나타나는 것은 우연이 아니다. 둘 다 ‘합(차분의 역)’을 ‘적분(미분의 역)’의 언어로 변환하는 과정에서 나타나기 때문이다.

이와 같은 대응 관계의 뿌리는 사실 한 줄의 연산자 항등식으로 요약된다. 테일러 전개를 사용하면 이동연산자 \(E\)는 미분연산자 \(D\)에 대하여 다음과 같이 표현된다. \[ \mathrm{E}f(x)=f(x+1)=\sum_{k\ge0}\frac{f^{(k)}(x)}{k!}=e^{D}f(x)\quad\Bigl(D=\tfrac{d}{dx}\Bigr) \] 해석적 함수나 형식적 거듭제곱급수의 맥락에서는 \(\mathrm{E}=e^{D}\)로 볼 수 있으므로 \[ \Delta=\mathrm{E}-\mathrm{I}=e^{D}-1 \] 이다. ‘이산미분은 연속 미분을 지수에 올린 것에서 \(1\)을 뺀 것’이라는 뜻이다. 합은 이 \(\Delta\)를 거꾸로 돌리는 일이고, 그 과정에서 \(\frac{t}{e^{t}-1}\)이라는 함수가 등장하는데, 이 함수의 테일러 계수가 바로 베르누이 수의 정의이다.¹⁰ 연속 세계의 미적분과 이산미적분이 두 얼굴을 가진 하나의 이론이라는 사실이, 이 한 줄 \(\Delta=e^{D}-1\)에 압축되어 있다. 여담으로, 오일러–매클로린 공식을 \(f(x)=\ln x\)에 적용하고, 상수를 결정하는 과정을 거치면, 유명한 스털링 근사 공식 \[ \ln(n!)\approx n\ln n-n+\tfrac12\ln(2\pi n) \] 이 나온다. 두 세계를 잇는 이 다리가, 차례곱 \(n!\)이 얼마나 빨리 증가하는지까지 알려 주는 셈이다.

여정을 마치며

지금까지 우리는 미분에 대응하는 차분에서 출발해, 연속 세계의 거듭제곱에 대응하는 하강거듭제곱, 적분에 대응하는 합, 부분적분에 대응하는 부분합, 그리고 \(e^x\)과 테일러 정리에 대응하는 \(2^x\)과 뉴턴 공식을 지나, 마지막으로 두 세계를 한 줄로 잇는 오일러–매클로린 공식까지 살펴보았다.

가장 인상적인 대목은, 이 평행 관계가 인위적으로 만든 비유가 아니라 자연스러운 대응이라는 점이다. \(\Delta=e^{D}-1\)이라는 등식은 이산미적분과 연속 미적분이 같은 연산자 이론의 두 가지 형태임을 말하고 있다. 미분에서 차분으로 건너오며 우리가 버린 ‘극한’은 사라진 게 아니다. 베르누이 수라는 보정항 속에 남아서 이산 세계와 연속 세계 사이의 차이를 채워준다.

좀 더 현실적인 수확도 있었다. 외워 두기만 했던 합 공식들이 개별적인 공식이 아니라 이산 세계에서 ‘적분’을 통해 자연스럽게 얻는 결과임을 알았다. 서로 무관해 보이던 결과들이 단 하나의 원리에서 얻어진다는 사실은 두고두고 곱씹어 볼 만한 우아한 발견이다.

이산미적분은 화려하게 등장하는 분야는 아니지만, 수치해석, 알고리즘 분석, 생성함수 이론 같은 곳에서 다양하게 활용된다. 이 평행 세계에 마음이 끌렸다면, 그레이엄, 커누스, 파타슈닉의 『구체 수학』(Concrete Mathematics)이 친절한 안내자가 되어 줄 것이다.¹¹

참고문헌

이산 세계를 더 파고들고 싶은 독자에게 권할 만한 문헌을 모았다. 본문의 거의 모든 내용은 사실상 첫 번째 책을 바탕으로 작성하였으므로, 딱 한 권만 고른다면 그것을 보면 된다.

먼저 본문 전체의 바탕이 된 교재이다.

Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). 『Concrete Mathematics: A Foundation for Computer Science』 (2nd ed.). Addison-Wesley. — 본문에서 다룬 차분, 하강 거듭제곱, 부정합과 기본정리, 부분합이 모두 제2장 「합(Sums)」의 ‘유한, 무한 미적분’ 절에 정리되어 있다. 이 글은 사실상 그 절을 따라 읽은 것이라 해도 좋다. 베르누이 수와 오일러–매클로린 공식은 뒤쪽 장에서 다룬다.
Mariconda, C., & Tonolo, A. (2016). 『Discrete Calculus: Methods for Counting』 (Unitext, Vol. 103). Springer. — 제목 그대로 이산미적분 그 자체를 다루는 비교적 최근 교재이다. 차분, 합 연산자를 출발점으로 삼아 조합론적 계산까지 체계적으로 설명한다. 학부 고학년이 한 권으로 공부하기에 좋다.

다음은 본문의 핵심 논점을 짧고 친절하게 풀어 쓴 해설이다. 두 편 모두 마지막 절에서 다룬 ‘두 미적분을 잇는 다리’와 관련된 내용을 담고 있다.

Lampret, V. (2001). “The Euler–Maclaurin and Taylor Formulas: Twin, Elementary Derivations.” Mathematics Magazine, 74(2), 109–122. — 본문 마지막 절의 주장, 곧 오일러–매클로린 공식과 테일러 공식이 ‘쌍둥이’라는 것을, 부분적분을 반복하는 단 하나의 계산으로 나란히 끌어낸다. 제목에 ‘twin’이 붙은 이유가 여기 있다. 학부 미적분만 알면 따라갈 수 있다.
Apostol, T. M. (1999). “An Elementary View of Euler’s Summation Formula.” The American Mathematical Monthly, 106(5), 409–418. — 오일러의 합 공식을 기초적인 방법으로 유도하면서, 베르누이 수가 어디서 어떻게 튀어나오는지 명료하게 설명한다. 본문에서 ‘합과 적분 사이를 연결하는 상수’라고만 적고 넘어간 부분을 직접 확인하고 싶다면 이 논문을 보면 된다.

이 분야의 골격은 이미 19세기에서 20세기 전반에 다져졌다. 본문 각주에서 언급한 불의 책을 비롯한 고전들이다.

Boole, G. (1860). 『A Treatise on the Calculus of Finite Differences』. Macmillan. — 본문에서 언급한, 불 대수로 유명한 그 조지 불이 쓴 차분 미적분 교과서다. 차분, 합, 차분방정식을 한데 묶어 다룬 초기 고전이라 할 만하다.
Milne-Thomson, L. M. (1933). 『The Calculus of Finite Differences』. Macmillan. Reprinted/2nd ed. 1951. — 20세기 전반의 표준 종합 참고서. 본문에서 맛만 본 내용을 폭넓게, 예제와 함께 설명한다. 지금 펼쳐 봐도 군더더기 없이 탄탄하다.

마지막으로, 본문 끝에서 \(\Delta=e^{D}-1\)이라는 한 줄로 표현한 ‘연산자 관점’을 제대로 파고들고 싶은 독자를 위한 문헌이다. 이쪽은 난도가 한 단계 높다.

Roman, S. (1984). 『The Umbral Calculus』. Academic Press. — 이동연산자와 차분을 기호적으로 다루는 ‘움브랄 계산(umbral calculus)’을 엄밀하게 정리한 책이다. 본문에서 살펴본 하강 거듭제곱, 뉴턴 공식, 베르누이 수 사이의 평행 관계가 사실은 하나의 대수 구조에서 유도된다는 사실을 보여 준다.
Rota, G.-C., Kahaner, D., & Odlyzko, A. (1973). “On the Foundations of Combinatorial Theory. VIII. Finite Operator Calculus.” Journal of Mathematical Analysis and Applications, 42(3), 684–760. — 이동연산자 \(\mathrm{E}\)와 \(\Delta=\mathrm{E}-\mathrm{I}\)를 본격적인 연산자로 다루는 ‘유한연산자 계산’의 토대를 놓은 논문이다. 본문 마지막 절이 어디로 이어지는지 궁금하다면 출발점으로 삼을 만하다.

위 문헌 중 한국어 번역본으로 확인되는 것은 첫 번째 책이다. 본문을 흥미롭게 읽었다면 부담 없이 펼쳐 볼 수 있다.

로널드 그레이엄, 도널드 커누스, 오렌 파타슈닉 (지음), 류광 (옮김). 『Concrete Mathematics 구체 수학』. 인사이트, 2018. (원서: Graham, Knuth, Patashnik, 『Concrete Mathematics』, 2nd ed., 1994.) — 위 Graham 외(1994)를 옮긴 번역본이다. 연습문제 해답까지 실려 있어 혼자 공부하기에 알맞다.

🍭