조화급수

3. 정의

조화급수는 다음과 같은 무한 급수이다.

:$$\backslash sum\_\{n=1\}^\backslash infty\backslash frac\{1\}\{n\}\; =\; 1\; +\; \backslash frac\{1\}\{2\}\; +\; \backslash frac\{1\}\{3\}\; +\; \backslash frac\{1\}\{4\}\; +\; \backslash frac\{1\}\{5\}\; +\; \backslash cdots$$

이 급수의 항들은 모두 양의 단위 분수들이다. 이 급수는 발산하는 급수이다. 급수의 더 많은 항들이 급수의 부분합에 포함될수록, 이 부분합의 값은 임의로 커져서 어떤 유한한 극한을 넘어선다. 발산하는 급수이기 때문에, 수치 값으로 평가될 수 있는 것이라기보다는 단위 분수를 결합한 추상적인 수학적 표현인 형식적인 합으로 해석해야 한다. 조화 급수의 발산에 대한 여러 가지 증명이 있다.^[45][46]

4. 발산성

조화 급수는 각 항이 0으로 수렴함에도 불구하고 그 합은 무한대로 발산한다. 발산 속도는 매우 느려서 ln(n)에 가깝다. 오일러-마스케로니 상수는 조화수열과 자연로그의 오차의 극한을 나타내는 상수이다. 조화 급수는 최초 $10^\{43\}$개의 항을 더해도 100을 넘지 않기 때문에, 수열의 항의 극한값이 0임에도 급수의 값은 수렴하지 않는 예로 자주 등장한다.^[51]

조화 급수는 다음과 같은 무한 급수이다.

:$\backslash sum\_\{n=1\}^\backslash infty\backslash frac\{1\}\{n\}\; =\; 1\; +\; \backslash frac\{1\}\{2\}\; +\; \backslash frac\{1\}\{3\}\; +\; \backslash frac\{1\}\{4\}\; +\; \backslash frac\{1\}\{5\}\; +\; \backslash cdots$

이 급수의 항들은 모두 양의 단위 분수들이며, 발산하는 급수이다.

조화 급수가 발산하기 때문에 발생하는 몇 가지 역설과 직관에 반하는 결과가 알려져 있다. 대표적인 예로 블록 쌓기 문제와 고무 밧줄 위의 개미 문제가 있다. 블록 쌓기 문제는 똑같은 도미노를 테이블 가장자리에 쌓을 때 도미노가 충분하다면 얼마든지 원하는 만큼 내밀 수 있다는 직관적이지 않은 결과를 보여준다.^{[47][50][48][49]} 고무줄 위의 애벌레 문제는 1미터 길이의 고무줄 위를 매분 1센티미터씩 기어가는 애벌레가 고무줄이 1분마다 1미터씩 늘어나는 상황에서 결국 끝에 도달할 수 있다는 역설적인 결과를 보여준다.

조화 급수의 발산은 매우 느리다. 부분합이 로그 증가를 보이기 때문이다. 특히 다음 식이 성립한다.

:$\backslash sum\_\{n=1\}^k\backslash frac\{1\}\{n\}\; =\; \backslash ln\; k\; +\; \backslash gamma\; +\; \backslash varepsilon\_k$

여기서 $\backslash gamma$는 오일러-마스케로니 상수이며, $\backslash varepsilon\_k$는 $k$가 무한대로 갈 때 0에 접근한다. 이 결과는 레온하르트 오일러가 증명하였다.

4. 1. 비교 판정법

발산을 증명하는 또 다른 방법은 각 분모를 다음으로 가장 큰 2의 거듭제곱으로 대체하여 비교하는 것이다.

:$$\backslash begin\{alignat\}\{8\}$$

1 & + \frac{1}{2} && + \frac{1}{3} && + \frac{1}{4} && + \frac{1}{5} && + \frac{1}{6} && + \frac{1}{7} && + \frac{1}{8} && + \frac{1}{9} && + \cdots \\[5pt]

{} \geq 1 & + \frac{1}{2} && + \frac{1}{\color{red}{\mathbf{4}}} && + \frac{1}{4} && + \frac{1}{\color{red}{\mathbf{8}}} && + \frac{1}{\color{red}{\mathbf{8}}} && + \frac{1}{\color{red}{\mathbf{8}}} && + \frac{1}{8} && + \frac{1}{\color{red}{\mathbf{16}}} && + \cdots \\[5pt]

\end{alignat}

같은 항을 묶으면 두 번째 급수가 발산한다는 것을 알 수 있다.

:$$\backslash begin\{align\}$$

& 1 + \left(\frac{1}{2}\right) + \left(\frac{1}{4} + \frac{1}{4}\right) + \left(\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}\right) + \left(\frac{1}{16} + \cdots + \frac{1}{16}\right) + \cdots \\[5pt]

{} = {} & 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \cdots.

\end{align}

조화 급수의 각 항이 두 번째 급수의 해당 항보다 크거나 같고, 모든 항이 양수이므로, 두 번째 급수가 발산하면 비교 판정법에 의해 조화 급수도 발산한다.

이 증명은 니콜 오렘이 1350년경에 제시했으며, 코시 응축 판정법은 이 논증을 일반화한 것이다.

4. 2. 적분 판정법

적분 판정법으로 조화 급수가 발산함을 보일 수 있다. 조화 급수는 오른쪽 그림에서 색칠한 사각형들의 넓이를 모두 더한 것이다. 곡선 $y\; =\; 1/x$ 아래쪽 넓이가 무한대로 발산하면, 조화 급수도 발산한다. 곡선 아래쪽의 넓이는 다음과 같이 적분으로 계산한다.

조화 급수의 최초 $k$ 항까지 더한 값($\backslash textstyle\; \backslash sum\_\{k=1\}^\backslash infty\; \backslash frac\{1\}\{k\}$)과 1부터 $k+1$ 까지의 구간을 적분한 값($\backslash int\_1^\{k+1\}\; \backslash frac\{1\}\{x\}\backslash ,dx\; \backslash ;$)은 적분판정법에 의하여 동시에 발산한다. 그런데

:$\backslash int\_1^\{\backslash infty\}\; \backslash frac\{1\}\{x\}\backslash ,dx\; \backslash ;=\backslash ;\backslash lim\_\{k\; \backslash to\; \backslash infty\}\backslash int\_1^\{k+1\}\; \backslash frac\{1\}\{x\}\backslash ,dx\; \backslash ;=\backslash ;\; \backslash lim\_\{k\; \backslash to\; \backslash infty\}\backslash ln(k+1)\; =\; \backslash infty$이다.

따라서 적분 판정법에 의해 조화 급수도 동시에 발산한다.

5. 성질

조화 급수는 리만 제타 함수에 1을 대입했을 때 얻어지는 수열이다. 부호가 번갈아 나타나는 교대 조화 급수는 수렴하며, 그 값은 $\backslash ln\; 2$이다. 교대 조화 급수는 절대 수렴하지 않는다.^[51] 따라서 항을 재배치하여 원하는 어떤 실수 값이든 만들어낼 수 있다.

다음과 같은 급수는 '''교대 조화 급수''' alternating harmonic series^영어로 알려져 있다.

:$$

\sum_{n = 1}^\infty \frac{(-1)^{n + 1}}{n} = 1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} - \cdots



이 급수의 수렴성은 라이프니츠 판정법에서 알 수 있다. 특히 이 급수의 합은 2의 자연로그와 같다. 즉,

:$1\; -\; \backslash frac\{1\}\{2\}\; +\; \backslash frac\{1\}\{3\}\; -\; \backslash frac\{1\}\{4\}\; +\; \backslash frac\{1\}\{5\}\; -\; \backslash cdots\; =\; \backslash ln\; 2$

가 성립한다. 이 식은 자연로그 함수의 테일러 급수인 메르카토르 급수의 특수한 경우이다.

역탄젠트 함수의 테일러 급수에서 유도되는 관련 급수로 다음과 같은 식이 있다.

: $$

\sum_{n = 0}^\infty \frac{(-1)^{n}}{2n+1} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots = \frac{\pi}{4}



이것은 라이프니츠의 π 공식으로 알려져 있다.

5. 1. 부분합 (조화수)

• $n$ 번째 조화수 $H\_n$와 $\backslash ln\; n$의 차이는 오일러-마스케로니 상수 $\backslash gamma$로 수렴한다.
• 서로 다른 번호의 조화수끼리의 차이는 결코 정수가 되지 않는다.
• $n\; =\; 1$을 제외하고 어떤 조화수도 정수가 아니다.

5. 2. 정수 조화수

6. 응용

조화 급수와 그 부분합은 여러 수학 문제의 해와 관련이 있다.^[1]

• '''사막 횡단 문제(지프 문제)'''는 알쿠인의 9세기 문제집인 ''청년을 날카롭게 하기 위한 제안''에 나오는 문제로, 지프(원래는 낙타)가 사막을 횡단하며 연료를 저장해 가면서 얼마나 멀리 갈 수 있는지를 묻는다. 조화급수의 발산은 충분한 연료가 있다면 어떤 거리라도 횡단 가능하다는 것을 보여준다.^[2]
• '''블록 쌓기 문제'''는 동일한 직사각형 블록들을 테이블에서 떨어지지 않게 쌓아 가장 멀리 튀어나오게 하는 문제이다. 블록들은 조화 급수에 따라 튀어나오도록 배치되며, 조화 급수의 발산은 블록 스택이 테이블 밖으로 얼마나 멀리 튀어나올 수 있는지에 제한이 없음을 의미한다.^[47]
• 1737년 레온하르트 오일러는 조화 급수가 각 항이 소수에서 나오는 오일러 곱과 같다는 것을 발견하고, 소수 역수의 합이 발산한다는 것을 증명하여 소수가 무한히 많다는 결론을 내렸다. 이는 메르텐스 정리로 확인되었고, 소수 정리의 전조로 여겨진다.
• 정수론에서 조화 급수는 1부터 $n$까지의 수의 평균 약수의 수와 관련이 있다. 페터 구스타프 르줜 디리클레는 평균 약수의 수가 $\backslash ln\; n+2\backslash gamma-1+O(1/\backslash sqrt\{n\})$임을 보였다. (빅 오 표기법으로 표현).^[1]
• '''쿠폰 수집가 문제'''는 모든 항목이 선택될 때까지 항목 집합에서 무작위 선택을 반복하는 문제로, 모든 항목을 수집하는 데 필요한 예상 시도 횟수는 ''nH''_''n''이다. 여기서 ''H''_''n''은 ''n''번째 조화수이다.^[4]
• 퀵 정렬 알고리즘은 조화수를 사용하여 분석할 수 있다. 평균 시간 복잡도 또는 기대 시간 분석에서, 모든 항목은 피벗으로 선택될 가능성이 동일하며, 재귀 과정에서 두 항목이 서로 비교될 확률은 최종 정렬 순서에서 두 항목을 구분하는 다른 항목의 수의 함수로 계산할 수 있다.

6. 1. 사막 횡단 문제 (지프 문제)

6. 2. 블록 쌓기 문제

6. 3. 소수와 약수

정수론에서 조화 급수와 관련된 문제는 1부터 $n$까지의 수의 평균 약수의 수에 관한 것이다. 이는 약수 함수의 평균 차수로 공식화된다. 조화 급수의 각 항을 $\backslash tfrac1n$의 다음으로 작은 정수 배수로 반올림하는 연산은 이 평균이 조화수와 작은 상수로 다르도록 한다. 페터 구스타프 르줜 디리클레는 평균 약수의 수가 $\backslash ln\; n+2\backslash gamma-1+O(1/\backslash sqrt\{n\})$임을 보였다(빅 오 표기법으로 표현). 최종 오차항을 더 정확하게 경계 짓는 것은 디리클레의 약수 문제로 알려진 미해결 문제로 남아 있다.^[1]

6. 4. 쿠폰 수집가 문제

일부 흔한 게임이나 오락은 가능한 모든 선택이 선택될 때까지 항목 집합에서 무작위 선택을 반복하는 것을 포함한다. 여기에는 트레이딩 카드 수집과 일련의 달리기 행사에서 시간의 모든 60가지 가능한 초를 얻는 것을 목표로 하는 파크런 빙고 완성이 포함된다.^[1] 이 문제의 더 심각한 응용 분야에는 품질 관리를 위해 제조된 제품의 모든 변형을 샘플링하는 것과 랜덤 그래프의 연결성이 있다.^[2][3] 이러한 형태의 상황에서, 총 ''n''개의 똑같이 가능한 항목 중에서 수집해야 할 항목이 ''k''개 남았을 때, 단일 무작위 선택에서 새로운 항목을 수집할 확률은 ''k/n''이고, 새로운 항목을 수집하는 데 필요한 예상 무작위 선택 횟수는 ''n/k''이다. ''n''에서 1까지 모든 ''k'' 값에 대해 합하면 모든 항목을 수집하는 데 필요한 총 예상 무작위 선택 횟수가 ''nH''_''n''이 되고, 여기서 ''H''_''n''은 ''n''번째 조화수이다.^[4]

6. 5. 퀵 정렬 알고리즘 분석

퀵 정렬 알고리즘은 조화수를 사용하여 분석할 수 있다. 이 알고리즘은 하나의 항목을 "피벗"으로 선택하고, 다른 모든 항목과 비교하여, 비교 결과에 따라 피벗 앞과 뒤에 놓이는 두 개의 항목 하위 집합을 재귀적으로 정렬하는 방식으로 작동한다. 평균 시간 복잡도(모든 입력 순열이 동일하게 발생할 가능성이 있다는 가정 하에) 또는 무작위로 선택된 피벗을 사용하는 최악의 경우 입력에 대한 기대 시간 분석에서, 모든 항목은 피벗으로 선택될 가능성이 동일하다. 이러한 경우, 재귀 과정에서 두 항목이 서로 비교될 확률은 최종 정렬 순서에서 두 항목을 구분하는 다른 항목의 수의 함수로 계산할 수 있다. 항목 $x$와 $y$가 $k$개의 다른 항목으로 구분되는 경우, 이 알고리즘은 재귀가 진행됨에 따라 $x$ 또는 $y$를 그 사이에 있는 다른 $k$개 항목보다 먼저 피벗으로 선택하는 경우에만 $x$와 $y$를 비교한다. 이 $k+2$개의 각 항목이 먼저 선택될 가능성이 동일하기 때문에, 이는 확률 $\backslash tfrac2\{k+2\}$로 발생한다. 알고리즘의 총 실행 시간을 제어하는 총 기대 비교 횟수는 모든 쌍에 대해 이러한 확률을 합산하여 계산할 수 있으며, 그 식은 다음과 같다.

$$\backslash sum\_\{i=2\}^n\backslash sum\_\{k=0\}^\{i-2\}\backslash frac2\{k+2\}=\backslash sum\_\{i=1\}^\{n-1\}2H\_i=O(n\backslash log\; n).$$

7. 관련 급수

'''일반 조화 급수'''(general harmonic series^영어)는 , 를 실수로 하고, 인 $\backslash sum\_\{n=0\}^\{\backslash infty\}\backslash frac\{1\}\{an+b\}$ 형태로 나타나는 급수이다. 비교 판정법에 의해, 임의의 일반 조화 급수가 발산한다는 것을 알 수 있다.^[53]

켐프너 급수(en:Kempner series)는 조화 급수의 항 중에서 분모의 십진 표기 각 자리 숫자 중 9가 나타나는 모든 항을 제거하여 얻어지는 급수이다. 열화 조화 급수는 수렴하며, 그 값은 22.92067...가 된다.^[57]

7. 1. 교대 조화 급수

7. 2. 리만 제타 함수

참조

_[1] 논문 A family of shifted harmonic sums
_[2] 논문 Problems to sharpen the young: An annotated translation of ''Propositiones ad acuendos juvenes'' 1992-03
_[3] 논문 Sums of reciprocals of integers missing a given digit 1979-05
_[4] 논문 Small values of signed harmonic sums
_[5] 논문 Partial sums of the harmonic series
_[6] 논문 The classical theory of zeta and $L$-functions
_[7] 서적 A Radical Approach to Real Analysis https://books.google[...] Mathematical Association of America
_[8] 서적 Introduction to Algorithms
_[9] 서적 Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics Joseph Henry Press
_[10] 논문 The Bernoullis and the harmonic series 1987-01
_[11] 논문 Variae observationes circa series infinitas https://scholarlycom[...]
_[12] 논문 On Riemann's rearrangement theorem for the alternating harmonic series http://eprints.gla.a[...]
_[13] 서적 Introduction to Random Graphs Cambridge University Press, Cambridge
_[14] 논문 The jeep once more or jeeper by the dozen 1970-05
_[15] 논문 How much is it going to cost me to complete a collection of football trading cards? 2013-04
_[16] 서적 Concrete Mathematics Addison-Wesley
_[17] 서적 Gamma: Exploring Euler's Constant Princeton University Press
_[18] 서적 Architecture and Geometry in the Age of the Baroque University of Chicago Press
_[19] 서적 The Pleasures of Probability Springer-Verlag
_[20] 서적 Propositiones arithmeticae de seriebus infinitis earumque summa finita J. Conrad 1689
_[21] 서적 Ars conjectandi, opus posthumum. Accedit Tractatus de seriebus infinitis https://books.google[...] Thurneysen 1713
_[22] 서적 Opera Omnia Marc-Michel Bousquet & Co. 1742
_[23] 논문 The harmonic series diverges again and again https://stevekifowit[...] American Mathematical Association of Two-Year Colleges 2006
_[24] 서적 The Art of Computer Programming, Volume I: Fundamental Algorithms Addison-Wesley
_[25] 논문 What's harmonic about the harmonic series? 2001-05
_[26] 논문 The "coupon collector's problem" and quality control 2009-03
_[27] 논문 A problem in cartophily 1938-10
_[28] 서적 Novae quadraturae arithmeticae, seu De additione fractionum Giacomo Monti 1650
_[29] 서적 Quaestiones super Geometriam Euclidis 1360
_[30] 논문 96.53 Partial sums of series that cannot be an integer 2012-11
_[31] 논문 Maximum overhang
_[32] 웹사이트 The coupon collector's problem (with Geoff Marshall) https://www.youtube.[...] YouTube 2022-02-12
_[33] 논문 Euler and the partial sums of the prime harmonic series
_[34] 서적 Mathematical Time Capsules: Historical Modules for the Mathematics Classroom Mathematical Association of America
_[35] 논문 The psi function
_[36] 논문 Review of ''A Radical Approach to Real Analysis'' by David M. Bressoud 2007-12
_[37] 논문 Could Euler have conjectured the prime number theorem?
_[38] 논문 On the $p$-adic valuation of harmonic numbers
_[39] 논문 Summing a curious, slowly convergent series 2008-06
_[40] 논문 Random harmonic series http://www.stat.ualb[...] 2003-05
_[41] 논문 Problem 52: Overhanging dominoes https://www.pme-math[...]
_[42] 논문 The three infinite harmonic series and their sums (with topical reference to the Newton and Leibniz series for $\backslash pi$)
_[43] 서적 Mathematics and its History Springer
_[44] 논문 Recent progress on the Dirichlet divisor problem and the mean square of the Riemann zeta-function
_[45] 서적 Quaestiones super Geometriam Euclidis c. 1360
_[46] 문서 Architecture and Geometry in the Age of the Baroque
_[47] 간행물 Problem 52: Overhanging dominoes
_[48] 웹사이트 ORメモランダム 古典的オーヴァーハングパズルをLPで解く https://orsj.org/wp-[...] 日本オペレーションズ・リサーチ学会 2024-07-22
_[49] 서적 モデリング: 広い視野を求めて (シリーズ:最適化モデリング 1) 第15章「双対問題の教えてくれるコト 近代科学社 2015-03-20
_[50] 서적 Concrete Mathematics Addison-Wesley
_[51] 웹사이트 Sequence A082912 in the On-Line Encyclopedia of Integer Sequences
_[52] url http://mathworld.wol[...]
_[53] 웹사이트 General Harmonic Series http://www.artofprob[...] Art of Problem Solving
_[54] 간행물 Random Harmonic Series 2003-05
_[55] url Schmuland's preprint of Random Harmonic Series http://www.stat.ualb[...]
_[56] 웹사이트 Infinite Cosine Product Integral http://mathworld.wol[...] 2014-11-09
_[57] 웹사이트 Nick's Mathematical Puzzles: Solution 72 http://www.qbyte.org[...]
_[58] 서적