합은 폭이 1인 막대들의 넓이이고, 적분은 곡선 아래의 넓이다. 그래서 줄어들거나 늘어나기만 하는 함수라면, 닫힌 꼴이 없는 합도 적분 두 개 사이에 끼워 크기를 정확히 어림할 수 있다. 조화수가 로그만큼 자라는 이유와, 정렬에 필요한 비교 횟수의 크기가 이렇게 나온다. 더 나아가 차분과 미분, 누적합과 적분은 공식까지 짝을 이룬다. 다만 함수가 오르내리면 막대와 곡선이 크게 어긋날 수 있다.
먼저 비교해 보기
표를 펼치기 전에 두 사례의 공통 구조와 대응 관계를 먼저 적어 본다.
| 이산수학: 누적합과 조화수 | 미분적분학: 적분과 로그 |
|---|---|
| \(a_k = \frac1k\), \(S_n = \sum_{k=1}^{n} a_k = H_n\) | \(f(x) = \frac1x\), \(F(x) = \int_1^x \frac{dt}{t} = \ln x\) |
| \(S_n - S_{n-1} = a_n\) | \(F'(x) = f(x)\) |
| \(\sum_{k=l}^{r} a_k = S_r - S_{l-1}\) | \(\int_a^b f = F(b) - F(a)\) |
| \(2^{k+1} - 2^k = 2^k\) | \((e^x)' = e^x\) |
| \(H_{1000} = 7.485\ldots\) | \(\ln 1000 = 6.907\ldots\) |
대응 관계
| 이산(합) | 연속(적분) | 공통 구조 |
|---|---|---|
| 차분 \(\Delta a_k = a_{k+1} - a_k\) | 도함수 \(f'\) | 변화율 |
| 합 \(\sum\) | 적분 \(\int\) | 누적 |
| 망원 합 \(\sum_{k=1}^{n}\Delta a_k = a_{n+1} - a_1\) | 기본정리 \(\int_a^b f' = f(b) - f(a)\) | 누적된 변화 = 끝값의 차 |
| \(2^k\) (\(\Delta 2^k = 2^k\)) | \(e^x\) (\((e^x)' = e^x\)) | 자기 자신이 변화율인 함수 |
| 하강 거듭제곱 \(k^{\underline m} = k(k-1)\cdots(k-m+1)\), \(\Delta k^{\underline m} = m\,k^{\underline{m-1}}\) | \(x^m\), \((x^m)' = m x^{m-1}\) | 거듭제곱 규칙 |
| \(H_n\) | \(\ln n\) | \(\frac1k\)와 \(\frac1x\)의 누적 |
| 부분합(교란법) | 부분적분 | 곱의 누적 |
거듭제곱 규칙에서 \(\sum_{k=0}^{n-1} k^{\underline m} = \frac{n^{\underline{m+1}}}{m + 1}\)이 \(\int_0^n x^m dx = \frac{n^{m+1}}{m+1}\)에 대응한다1.
어디까지 같은가
- 가장 큰 항까지는 같고, 가장자리가 다르다. \(\sum_{k=1}^{n} k = \frac{n^2}{2} + \frac n2\)이고 \(\int_0^n x\,dx = \frac{n^2}{2}\)이다. 차이 \(\frac n2\)는 막대의 삐져나온 삼각형들이다.
- 보통의 거듭제곱은 차분과 맞지 않는다. \(\Delta k^2 = 2k + 1\)이지 \(2k\)가 아니다. 거듭제곱 규칙이 그대로 통하려면 하강 거듭제곱을 써야 한다.
- 곱의 법칙에 밀림이 생긴다. \(\Delta(uv)_k = u_k\,\Delta v_k + v_{k+1}\,\Delta u_k\)이다. 한쪽이 한 칸 밀린 값이다.
- 함수가 오르내리면 끼우기가 무너진다. \(f(x) = \sin^2(\pi x)\)는 모든 정수에서 0이라 \(\sum_{k=1}^{n} f(k) = 0\)이지만, \(\int_0^n f = \frac n2\)이다. 아래 정리가 “줄어들기만” 또는 “늘어나기만”을 요구하는 이유다.
이 연결로 얻는 것
\(f\)가 \([1, n + 1]\)에서 음이 아니고 줄어들기만 하면
\[\int_1^{n+1} f(x)\,dx \le \sum_{k=1}^{n} f(k) \le f(1) + \int_1^{n} f(x)\,dx.\]늘어나기만 하면 부등호 방향을 바꿔 \(\int_0^{n} f \le \sum_{k=1}^{n} f(k) \le \int_1^{n+1} f\)이다(\(f\)가 \([0, n+1]\)에서 음이 아니고 늘어나기만 할 때)2.
증명
줄어드는 \(f\)에서 \(x \in [k, k+1]\)이면 \(f(k + 1) \le f(x) \le f(k)\)이다. 적분하면 \(f(k + 1) \le \int_k^{k+1} f \le f(k)\). 왼쪽 부등식을 \(k = 1, \dots, n - 1\)에서 더하면 \(\sum_{k=2}^{n} f(k) \le \int_1^n f\)라 위쪽 한계가, 오른쪽 부등식을 \(k = 1, \dots, n\)에서 더하면 아래쪽 한계가 나온다. ∎
막대 하나가 합의 한 항 \(\frac1k\)이다. 왼쪽처럼 막대를 \([k, k+1]\)에 세우면 막대 꼭대기가 곡선 위로 나와서 합이 넓이보다 크다. 오른쪽처럼 \([k-1, k]\)로 한 칸 당기면 막대가 곡선 아래로 들어가서 합이 넓이보다 작다. 첫 항 1은 오른쪽에서 빠지므로 위쪽 한계에 따로 더한다3.
이 정리로 이산수학의 어림들을 로그와 거듭제곱의 정확한 상수까지 끌어올린다.
| 합 | 끼운 결과 | 뜻 |
|---|---|---|
| \(H_n = \sum \frac1k\) | \(\ln(n + 1) \le H_n \le 1 + \ln n\) | \(H_n = \ln n + O(1)\) |
| \(\ln n! = \sum \ln k\) | \(n\ln n - n + 1 \le \ln n! \le (n + 1)\ln(n + 1) - n\) | \(n! \approx (n/e)^n\) (다항식 인수 차이) |
| \(\sum k^d\) | \(\frac{n^{d+1}}{d+1} \le \sum_{k=1}^n k^d \le \frac{(n+1)^{d+1}}{d+1}\) | 최고차항 \(\frac{n^{d+1}}{d+1}\) |
더 나아가 \(H_n - \ln n\)은 \(n\)이 커지면 줄어들기만 하고 0보다 크다. 그래서 어떤 상수로 수렴하고, 그 값이 오일러–마스케로니 상수 \(\gamma \approx 0.5772\)다2. 줄어드는 이유는 \((H_{n+1} - \ln(n+1)) - (H_n - \ln n) = \frac{1}{n+1} - \ln\left(1 + \frac1n\right) < 0\)이기 때문이다(\(\ln(1 + \frac1n) = \int_n^{n+1}\frac{dx}{x} > \frac{1}{n+1}\)).
정렬의 하한. \(\lg n! = \frac{\ln n!}{\ln 2} \approx n\lg n - n\lg e \approx n\lg n - 1.443n\)이다. 합의 계산과 어림에서 본 “비교 정렬은 \(\lg n!\)번 이상 비교”가 구체적인 수로 바뀐다. \(n = 1000\)이면 약 8,530번이다.
- 알고리즘에서: 누적 합과 차분 배열은 구간 합을 누적 합 두 값의 차 \(S_r - S_{l-1}\)로 구하고, 구간 양 끝에만 표시했다가 앞에서부터 더해 배열을 되찾는 차분 배열로 망원 합을 쓴다. 병합 정렬은 최악에도 비교를 \(n \lg n\)번쯤 해서 위 하한과 맨 앞 항이 같다. 그래서 정렬과 정렬 기준은
sorted보다 빠른 비교 정렬을 직접 짤 일이 없다고 본다.
전이 문제
반복문의 \(i\)번째 바퀴가 \(\sqrt i\)에 비례하는 일을 한다(예: \(i\) 이하의 약수 후보를 \(\sqrt i\)까지만 검사). \(n\)바퀴의 총비용 \(\sum_{i=1}^{n}\sqrt i\)를 위아래로 끼우고, \(n = 10^6\)일 때 어림하라.
답
\(\sqrt x\)는 늘어나기만 하므로 \(\int_0^n\sqrt x\,dx \le \sum \le \int_1^{n+1}\sqrt x\,dx\), 즉 \(\frac23 n^{3/2} \le \sum \le \frac23\left((n+1)^{3/2} - 1\right)\). \(n = 10^6\)이면 \(666{,}666{,}667\)과 \(666{,}667{,}666\) 사이이고, 실제 값은 약 \(666{,}667{,}166\)이다. 결국 \(\Theta(n^{3/2})\)다.
확인 문제
C1 H₁₀₀₀을 적분으로 위아래에서 끼우라.
답: \(\ln 1001 \approx 6.909 \le H_{1000} \le 1 + \ln 1000 \approx 7.908\). 실제 값은 \(7.4855\)이고, \(\ln 1000 + \gamma \approx 7.4850\)과 매우 가깝다.
C2 적분으로 합을 끼우는 정리에 “줄어들기만(늘어나기만) 하는 함수” 조건이 필요한 이유를 반례로 보여라.
답: \(f(x) = \sin^2(\pi x)\)는 모든 정수에서 0이라 \(\sum_{k=1}^{n} f(k) = 0\)인데 \(\int_0^n f = \frac n2\)이다. 정수 사이에서 오르내리는 모양을 막대가 전혀 보지 못한다.
C3 ∫₀ⁿ x² dx = n³/3에 대응하는 합 공식을 하강 거듭제곱으로 쓰고, n = 4에서 확인하라.
답: \(\sum_{k=0}^{n-1} k^{\underline 2} = \frac{n^{\underline 3}}{3}\), 즉 \(\sum_{k=0}^{n-1} k(k - 1) = \frac{n(n-1)(n-2)}{3}\). \(n = 4\)이면 \(0 + 0 + 2 + 6 = 8 = \frac{4 \cdot 3 \cdot 2}{3}\).
-
Graham·Knuth·Patashnik, Concrete Mathematics, 2.6절 “Finite and Infinite Calculus”(차분 \(\Delta\), 하강 거듭제곱, 부분합). ↩
-
Lehman·Leighton·Meyer, Mathematics for Computer Science, 14장 “Sums and Asymptotics”(적분으로 합 끼우기, 조화수, 스털링 근사). 같은 부등식이 OpenStax, Calculus Volume 2, 5.3절 “The Divergence and Integral Tests”의 적분 판정 증명에 쓰인다. ↩ ↩2
-
16_sum-integral-bounds_plot.py로 그렸고, \(\ln 9 \le H_8 \le 1 + \ln 8\)과 \(n \le 10^4\)에서 \(\ln(n + 1) \le H_n \le 1 + \ln n\)을 같은 코드로 확인했다. ↩