Гармонические числа

Гармонические числа (harmonic numbers) — числа

Hn   ⁣=def   ⁣1+12+13+14+⋯+1n−1+1n=∑k=1n1kH_n \defeq 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dotsb + \frac{1}{n-1} + \frac{1}{n} = \sum\limits_{k=1}^n \frac{1}{k}

Эти числа повсеместно встречаются в анализе алгоритмов.

Асимптотические формулы

Важное свойство гармонических чисел, основа их асимптотического анализа — Hn∼ln⁡nH_n \sim \ln n. Доказать это можно, рассмотреть если ограничить HnH_n с двух сторон интегралами

∫1ndxx   ⁣⩽   ⁣Hn⩽1+∫1ndxx  ⟺  ln⁡n⩽Hn⩽1+ln⁡n\int\limits_{1}^{n} \frac{dx}{x} \;\! \le \;\! H_n \le 1 + \int\limits_{1}^n \frac{dx}{x} \iff \ln n \le H_n \le 1 + \ln n

Делим все части неравенства на ln⁡n\ln n и переходим к пределу.

Hn∼ln⁡nпри n→∞H_n \sim \ln n \quad\text{при}~ n \to \oo

Есть более общая формула, использующая константу Эйлера-Маскерони γ   ⁣=def   ⁣lim⁡n→∞(Hn−ln⁡n)\gamma \defeq \lim\limits_{n \to \oo} \big( H_n - \ln n \big)

Hn=γ+ln⁡n+12n−∑k=1∞B2k2k⋅n2kH_n = \gamma + \ln n + \frac{1}{2n} - \sum\limits_{k=1}^\oo \frac{B_{2k}}{2k \cdot n^{2k}}

Асимптотическую формулу можно применять для нахождение времени работы алгоритмов. Например, следующая конструкция достаточно часто встречается

for int i = 1; i <= n; i++: for int j = i; j <= n; j += i: do something

Количество итераций вложенного цикла, которое совпадает с количеством выполнения куска кода do something, равно

∑j=1n⌊nj⌋   ⁣⩽   ⁣∑j=1nnj=n⋅Hn∼nln⁡n\sum\limits_{j=1}^n \left\lfloor \frac{n}{j} \right\rfloor \;\! \le \;\! \sum\limits_{j=1}^n \frac{n}{j} = n \cdot H_n \sim n \ln n

Гармонические суммы

Гармонические числа постоянно встречаются в анализе алгоритмов, поэтому полезно будет заранее получить много полезных свойств, которыми обладают суммы с гармоническими числами.

Степенные суммы

Вычислим сумму гармонических чисел ∑k=1nHk\sum\limits_{k=1}^n H_k, поменяв порядок суммирования

∑k=1nHk=∑k=1n∑j=1k1j=∑j=1nn+1−jj=(n+1) Hn−n\sum\limits_{k=1}^n H_k = \sum\limits_{k=1}^n \sum\limits_{j=1}^{k} \frac{1}{j} = \sum\limits_{j=1}^n \frac{n+1-j}{j} = (n+1) \, H_n - n

Давайте теперь вычислим общую сумму ∑k=1nkm Hk\sum\limits_{k=1}^n k^m \, H_k.

∑k=1nk Hk=∑k=1n∑j=1k1j=∑j=1nn+1−jj=(n+1) Hn−n\sum\limits_{k=1}^n k \, H_k = \sum\limits_{k=1}^n \sum\limits_{j=1}^{k} \frac{1}{j} = \sum\limits_{j=1}^n \frac{n+1-j}{j} = (n+1) \, H_n - n

Способ вычисления. Поскольку сама формула суммы очень большая и сложная, я просто покажу, как её можно считать, а потом приведу некоторые частные значения.

Рассмотрим исходную сумму ∑k=1nkm Hk\sum\limits_{k=1}^n k^m \, H_k, распишем гармоническое число и поменяем порядок суммирования

∑k=1nkm Hk=∑k=1nkm∑j=1k1j=∑j=1n1j∑k=jnkm\sum\limits_{k=1}^n k^m \, H_k = \sum\limits_{k=1}^n k^m \sum\limits_{j=1}^k \frac{1}{j} = \sum\limits_{j=1}^n \frac{1}{j} \sum\limits_{k=j}^n k^m

Внутренняя сумма — это сумма mm-х степеней чисел от jj до nn. Эту сумму можно вычислить как разность сумм Фаульхабера для nn и для jj. Суммы Фаульхабера мною подробно анализировались в разделе «Суммы kk-х степеней» статьи «Числа Бернулли»

∑k=jnkm=∑k=1nkm−∑k=1j−1km=1m+1∑ℓ=0m(m+1ℓ) Bℓ (nm+1−ℓ−(j−1)m+1−ℓ)\sum\limits_{k=j}^n k^m = \sum\limits_{k=1}^n k^m - \sum\limits_{k=1}^{j-1} k^m = \frac{1}{m+1} \sum\limits_{\ell=0}^m \binom{m+1}{\ell} \, B_\ell \, \bigl( n^{m+1-\ell} - (j-1)^{m+1-\ell} \bigr)

Подставляем и считаем

∑k=1nkm Hk=1m+1∑ℓ=0m(m+1ℓ) Bℓ⋅∑j=1nnm+1−ℓ−(j−1)m+1−ℓj==1m+1∑ℓ=0m(m+1ℓ) Bℓ⋅(nm+1−ℓ Hn−∑j=1n(j−1)m+1−ℓj)\align{ \sum\limits_{k=1}^n k^m \, H_k &= \frac{1}{m+1} \sum\limits_{\ell=0}^m \binom{m+1}{\ell} \, B_\ell \cdot \sum\limits_{j=1}^n \frac { n^{m+1-\ell} - (j-1)^{m+1-\ell} } {j} = \\ &= \frac{1}{m+1} \sum\limits_{\ell=0}^m \binom{m+1}{\ell} \, B_\ell \cdot \left( n^{m+1-\ell} \, H_n - \sum\limits_{j=1}^n \frac{(j-1)^{m+1-\ell}}{j} \right) }

Далее для вычисления нужно разложить (j−1)m+1−ℓ(j-1)^{m+1-\ell} по формуле бинома Ньютона

∑j=1n(j−1)m+1−ℓj=∑j=1n∑i=0m+1−ℓ(m+1−ℓi) (−1)m+1−ℓ−i ji−1=∑i=0m+1−ℓ(m+1−ℓi) (−1)m+1−ℓ−i∑j=1nji−1==(−1)m+1−ℓ Hn+∑i=1m+1−ℓ(m+1−ℓi) (−1)m+1−ℓ−i∑j=1nji−1\align{ \sum\limits_{j=1}^n \frac{(j-1)^{m+1-\ell}}{j} &= \sum\limits_{j=1}^n \sum\limits_{i=0}^{m+1-\ell} \binom{m+1-\ell}{i} \, (-1)^{m+1-\ell-i} \, j^{i-1} = \sum\limits_{i=0}^{m+1-\ell} \binom{m+1-\ell}{i} \, (-1)^{m+1-\ell-i} \sum\limits_{j=1}^n j^{i-1} =\\ &= (-1)^{m+1-\ell} \, H_n + \sum\limits_{i=1}^{m+1-\ell} \binom{m+1-\ell}{i} \, (-1)^{m+1-\ell-i} \sum\limits_{j=1}^n j^{i-1} }

Теперь осталась сумма Фаульхабера

∑j=1nji−1=1i∑s=0i−1(is) Bs ni−s\sum\limits_{j=1}^n j^{i-1} = \frac{1}{i} \sum\limits_{s=0}^{i-1} \binom{i}{s} \, B_s \, n^{i-s}

Можно собрать всё воедино

∑k=jnkm Hk=1m+1∑ℓ=0m(m+1ℓ) Bℓ⋅(nm+1−ℓ Hn+(−1)m−ℓ Hn++∑i=1m+1−ℓ(m+1−ℓi) (−1)m−ℓ−ii∑s=0i−1(is) Bs ni−s)\align{ \sum\limits_{k=j}^n k^m \, H_k = \frac{1}{m+1} \sum\limits_{\ell=0}^m \binom{m+1}{\ell} \, B_\ell \cdot \Biggl(& n^{m+1-\ell} \, H_n + (-1)^{m-\ell} \, H_n + \\ &+ \sum\limits_{i=1}^{m+1-\ell} \binom{m+1-\ell}{i} \, \frac{(-1)^{m-\ell-i}}{i} \sum\limits_{s=0}^{i-1} \binom{i}{s} \, B_s \, n^{i-s} \Biggr) }

Теперь некоторые значения сумм

∑k=1nk Hk=n (n+1)2⋅Hn−n (n−1)4∑k=1nk2 Hk=n (n+1) (2n+1)6⋅Hn−n (n−1) (4n+1)36∑k=1nk3 Hk=n2 (n+1)24⋅Hn−n (n−1) (n+1) (3n−2)48∑k=1nk4 Hk=n (n+1) (2n+1) (3n2+3n−1)30⋅Hn−n (n−1) (72n3+27n2−103n−28)1800∑k=1nk5 Hk=n2 (n+1)2 (2n2+2n−1)12⋅Hn−n (n−1) (n+1) (2n−1) (10n2−n−18)720\align{ \sum\limits_{k=1}^n k \, H_k &= \frac{n \, (n+1)}{2} \cdot H_n - \frac{n \, (n-1)}{4} \\ \sum\limits_{k=1}^n k^2 \, H_k &= \frac{n \, (n+1) \, (2n+1)}{6} \cdot H_n - \frac{n \, (n-1) \, (4n+1)}{36} \\ \sum\limits_{k=1}^n k^3 \, H_k &= \frac{n^2 \, (n+1)^2}{4} \cdot H_n - \frac{n \, (n-1) \, (n+1) \, (3n-2)}{48} \\ \sum\limits_{k=1}^n k^4 \, H_k &= \frac{n \, (n+1) \, (2n+1) \, (3n^2+3n-1)}{30} \cdot H_n - \frac{n \, (n-1) \, (72n^3+27n^2-103n-28)}{1800} \\ \sum\limits_{k=1}^n k^5 \, H_k &= \frac{n^2 \, (n+1)^2 \, (2n^2+2n-1)}{12} \cdot H_n - \frac{n \, (n-1) \, (n+1) \, (2n-1) \, (10n^2-n-18)}{720} \\ }

Обобщённые гармонические числа

Можно рассматривать суммы обратных ss-х степеней натуральных чисел. Тогда мы получим обобщённые гармонические числа, которые тоже иногда встречаются при анализе алгоримтов

Hn(s)   ⁣=def   ⁣1+12s+13s+14s+⋯+1(n−1)s+1ns=∑k=1n1ksH^{(s)}_n \defeq 1 + \frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{4^s} + \dotsb + \frac{1}{(n-1)^s} + \frac{1}{n^s} = \sum\limits_{k=1}^n \frac{1}{k^s}

Обобщённые гармонические числа можно использовать, например, для приближения обычных гармонических чисел. Посмотрим на ряд

ln⁡(kk−1)=1k+12k2+13k3+14k4+⋯=∑j=1∞1j⋅kj\ln \left( \frac{k}{k-1} \right) = \frac{1}{k} + \frac{1}{2k^2} + \frac{1}{3k^3} + \frac{1}{4k^4} + \dotsb = \sum\limits_{j=1}^\oo \frac{1}{j \cdot k^j}

Справа написано ln⁡k−ln⁡(k−1)\ln k - \ln (k-1), а значит можно выразить ln⁡n−ln⁡1\ln n - \ln 1 как сумму

ln⁡n−ln⁡1=∑k=2nln⁡(kk−1)=∑k=2n∑j=1∞1j⋅kj=∑j=1∞Hn(j)−1j\ln n - \ln 1 = \sum\limits_{k=2}^n \ln \left( \frac{k}{k-1} \right) = \sum\limits_{k=2}^n \sum\limits_{j=1}^\oo \frac{1}{j \cdot k^j} = \sum\limits_{j=1}^\oo \frac{H^{(j)}_n - 1}{j}

Отсюда можно, например, получить значение γ\gamma с большой сходимостью, порядка 1/2s1/2^s

Hn−ln⁡n=1−12(Hn(2)−1)−13(Hn(3)−1)−14(Hn(4)−1)−⋯=1−∑s=2∞Hn(j)−1jH_n - \ln n = 1 - \frac{1}{2} \big( H^{(2)}_n - 1 \big) - \frac{1}{3} \big( H^{(3)}_n - 1 \big) - \frac{1}{4} \big( H^{(4)}_n - 1 \big) - \dotsb = 1 - \sum\limits_{s=2}^\oo \frac{H^{(j)}_n - 1}{j}

Переходя к пределу n→∞n \to \oo получаем

γ=1−∑s=2∞ζ(j)−1j\gamma = 1 - \sum\limits_{s=2}^\oo \frac{\zeta(j) - 1}{j}

где ζ(j)\zeta(j) — дзета-функция Римана, ζ(s)=∑k=1∞1/ks\zeta(s) = \sum\limits_{k=1}^\oo 1/k^s

Значения ⌊n/j⌋\lfloor n/j \rfloor