조화급수(Harmonic series)

항이 0으로 줄어드는데도 합이 무한대가 될 수 있을까요? $1 + \tfrac12 + \tfrac13 + \cdots$가 그렇습니다. $n =$ 까지 더하면 , $\ln n =$ 이고 차이는 오일러의 이름을 딴 상수 $\gamma \approx 0.5772$에 다가갑니다. 부분합⁠(partial sum)⁠이 한 값에 다가가지 않으면 발산한다고 하는데, 이 급수⁠(series)⁠처럼 부분합이 어떤 수든 결국 넘어서는 것이 그 한 가지입니다.

왼쪽 그림에서 폭 1인 막대들의 높이가 $1/k$입니다. k번째 막대는 x = k부터 k + 1까지 걸쳐 있고, 그 구간에서 곡선 $1/x$보다 높습니다. 그래서 n개 막대의 넓이⁠(area)⁠ 합 $H_n$은 1부터 n + 1까지 곡선 아래 넓이, 곧 자연로그⁠(natural logarithm)⁠ $\ln(n+1)$보다 큽니다. 그리고 로그는 끝없이 자랍니다. 느리지만 멈추지 않습니다. 합이 100을 넘으려면 약 $1.5 \times 10^{43}$개의 항이 필요합니다.

로그를 쓰지 않는 더 오래된 증명도 있습니다. 발산한다는 사실을 처음 증명한 사람으로 알려진 이는 14세기 프랑스의 학자 니콜 오렘입니다. $\tfrac13 + \tfrac14 \gt \tfrac12$, $\tfrac15 + \cdots + \tfrac18 \gt \tfrac12$처럼 항을 2개, 4개, 8개, …씩 묶으면 1/2보다 큰 묶음이 끝없이 나오기 때문입니다. 반면 제곱의 역수⁠(inverse)⁠ 합은 π²/6으로 수렴⁠(convergence)⁠하고, 비율이 일정한 등비급수⁠(geometric series)⁠도 수렴합니다.

소수⁠(prime number)⁠의 역수만 골라 더한 $\tfrac12 + \tfrac13 + \tfrac15 + \tfrac17 + \cdots$도 발산합니다. 1737년 오일러가 보인 사실로, n까지의 소수에 대한 합은 $\ln\ln n$만큼, 조화급수보다도 느리게 자랍니다. 소수가 유한 개라면 이 합은 유한한 수일 테니, 발산한다는 사실 자체가 소수가 무한히 많다는 증명이 됩니다. 소수 정리⁠(prime number theorem)⁠에 따르면 x 근처의 수 가운데 소수가 차지하는 비율(밀도)은 약 $1/\ln x$입니다. 이 밀도를 곱해 1/x를 적분⁠(integral)⁠하면 $\int dx/(x\ln x) = \ln\ln x$로 같은 증가 속도⁠(velocity)⁠가 나옵니다. 이것은 어림이고, 정확한 증명은 따로 필요합니다(1874년 메르텐스). 이런 "넓이로 합을 가늠하는" 방법은 리만 합⁠(Riemann sum)⁠을 거꾸로 쓰는 것입니다.

합을 곡선 아래 넓이로 어림하는 요령은 계승⁠(factorial)⁠ $n! = 1 \times 2 \times \cdots \times n$에도 통합니다. $\ln n! = \ln 1 + \ln 2 + \cdots + \ln n$을 곡선 ln x 아래 넓이로 어림하면 스털링 공식⁠(Stirling's formula)⁠이 나옵니다.

퀵정렬⁠(quicksort)⁠은 1960년 무렵 영국의 토니 호어가 고안한 정렬 방법으로, 기준값 하나를 골라 그보다 작은 것과 큰 것으로 나누는 일을 되풀이합니다(정렬 알고리즘⁠, sorting algorithm⁠). 기준값을 무작위로 고르면 n개를 정렬할 때 평균⁠(mean)⁠ 비교 횟수가 약 $2n\ln n$입니다. i번째로 작은 원소⁠(element)⁠와 j번째로 작은 원소가 서로 비교될 확률⁠(probability)⁠이 $2/(j-i+1)$이라, 이를 모든 쌍에 대해 더하면 조화급수가 나오기 때문입니다(무작위 알고리즘⁠, randomized algorithm⁠).

1962년 데이비드 게일과 로이드 섀플리가 발표한 짝짓기 절차에서는 한쪽이 선호 순서대로 청혼하고, 다른 쪽은 지금 짝보다 마음에 드는 청혼이 오면 짝을 바꿉니다. 선호가 무작위이면 청혼 횟수의 평균이 대략 $n\ln n$로 자라는데, 이것 역시 조화급수에서 나옵니다(안정 매칭⁠, stable matching⁠).

지프의 법칙⁠(Zipf's law)⁠에 따르면 k번째로 흔한 단어의 빈도는 1/k에 비례합니다. 어휘가 n개라면 모든 단어의 빈도 비율을 더해 1이 되어야 하니, 비례 상수는 $1/(1 + \tfrac12 + \cdots + \tfrac1n)$, 곧 조화급수 부분합의 역수입니다.