조화수
조화수는 수학에서 조화수열(harmonic sequence)의 부분합을 가리키는 용어이다.
정수 $n \ge 1$ 에 대해 조화수 $H_n$ 은
$$ H_n = \sum_{k=1}^{n} \frac{1}{k}=1+\frac12+\frac13+\dots+\frac1n $$
와 같이 정의된다. 이 수열은 무한 급수 $\displaystyle\sum_{k=1}^{\infty}\frac{1}{k}$ 의 부분합이므로, $n$ 이 커짐에 따라 점차 증가하지만, 발산한다는 것이 알려져 있다.
주요 성질
-
점근식
$$ H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^{2}} + O!\left(\frac{1}{n^{4}}\right) $$ 여기서 $\gamma \approx 0.5772156649$ 는 오일러‑마스케로니 상수이다. -
단조 증가
각 항이 양수이므로 $H_{n+1}=H_n+\frac1{n+1}>H_n$ 이다. -
비정수성
$n\ge 2$ 인 경우 $H_n$ 은 유리수가 아니다(예: $H_2=3/2$ 은 유리하지만, $n\ge 3$ 에서는 기약분수 형태가 아닌 경우가 존재한다). 특히 $H_{p-1}$ (단일 소수 $p$ 에 대해) 은 $\frac{a}{p}$ 형태로 나타날 수 있다. -
정수와의 관계
$H_n$ 가 정수가 되는 경우는 $n=1$ 뿐이다. $n\ge 2$ 에서는 항상 비정수이다. -
응용
- 분석학: 조화 급수는 로그함수와 연관되어 극한과 적분에 자주 등장한다.
- 조합론: $H_n$ 은 기대값을 구하는 문제에서, 예를 들어 “랜덤 순열에서 고정점(자기 자리) 기대값” 등에 사용된다.
- 알고리즘 분석: 평균 비교 횟수가 $O(n \log n)$ 인 정렬 알고리즘(예: 퀵정렬)의 기대 시간 복잡도 분석에 조화수가 등장한다.
관련 용어
- 조화수열: $\displaystyle \frac{1}{1},\frac{1}{2},\frac{1}{3},\dots$ 로 이루어진 수열.
- 조화급수: $\displaystyle\sum_{k=1}^{\infty}\frac{1}{k}$ 로, 발산한다는 것이 알려져 있다.
- 오일러‑마스케로니 상수 $\gamma$: 조화수와 자연로그의 차이가 수렴하는 상수.
참고
조화수는 전 세계 수학 교과서와 전문 서적에서 “harmonic number” 라는 영문 명칭으로 표기되며, 한국어 문헌에서는 ‘조화수’ 라는 용어가 일반적으로 사용된다. 따라서 백과사전이나 학술 데이터베이스에서도 해당 용어를 확인할 수 있다.
