Liczby harmoniczne

Na początek coś z fizyki rozrywkowej. Przypuśćmy, że chcemy ułożyć na stole stos kart, tak aby nawis utworzony przez karty wystające poza krawędź stołu był maksymalny. Oczywiście jeżeli ,,stos'' składa się z jednej karty kładziemy ją tak, aby środek masy karty przypadał na krawędzi stołu. (Wszystkie karty kładziemy tak, aby ich krótsze brzegi były równoległe do krawędzi stołu). W przypadku dwóch kart karta dolna ,,robi za stół'' , to znaczy środek masy karty górnej leży nad krawędzią dolnej, natomiast środek masy całej struktury (dwóch kart) - nad krawędzią stołu.

Rekurencja wygląda dość prosto. Najwygodniej będzie oznaczyć przez d_n odległość krawędzi karty ,,wierzchniej'' od krawędzi karty n-tej od góry. Wówczas d₁=0, natomiast dla stosu n kart, dla którego stół ,,robi'' za kartę (n+1)-szą, d_n+1 to współrzędna środka masy układu n kart. Znowu dla wygody przyjmijmy długość karty równą dwóm jednostkom. Współrzędna środka masy karty o numerze k (cały czas liczymy je od góry), liczona względem prawego brzegu nawisu to odległość d_k powiększona o połowę długości karty, a więc d_k+1. Dla n kart mamy, zgodnie z definicja środka masy:

$\begin{displaymath}d_{n+1} = \frac { (d_1+1) + (d_2+ 1) + \ldots + (d_n+1 ) } { n}. \end{displaymath}$

Powyższy wzór warto przekształcić do postaci jawnej rekurencji. Kładąc raz n=k, a raz n=k-1 mamy:

$\begin{eqnarray*}kd_{k+1} & = & k + d_1 + \ldots + d_{k-1} + d_k,\\ (k-1) d_{k} & = & k -1 + d_1 + \ldots + d_{k-1} + d_{k-1}.\\ \end{eqnarray*}$

Odejmujemy równania stronami:

kd_k+1 - (k-1) d_k = 1 +d_k

(1)

a więc

$\begin{displaymath} d_{k+1} = d_k + \frac 1 k.\end{displaymath}$

(2)

Pierwsza karta wystaje o jedną jednostkę poza drugą, druga - o pół jednostki poza trzecią, trzecia - o jedną trzecią jednostki poza czwartą, .... Jeżeli to nie wynika z rysunku to przepraszam, robiłem go całkowicie na oko. Pamiętając, że d₁ = 1 i stosując wzór k-krotnie dostaniemy:

$\begin{displaymath}d_{k+1} = 1 + \frac 1 2 + \frac 1 3 + \ldots + \frac{1}{k-1} + \frac 1 k = \sum_{j=1}^k \equiv H_k, \end{displaymath}$

gdzie liczbę H_k nazywamy k-tą liczbą harmoniczną. Przypominam: średnia harmoniczna dwóch (lub więcej) liczb to odwrotność sumy ich odwrotności. Na przykład oporność zastępcza układu oporników połączonych równolegle jest równa średniej harmonicznej poszczególnych oporności. Wiemy wszyscy, że nieskończona suma

$\begin{displaymath}\sum_{n=1}^\infty \frac 1 n \end{displaymath}$

(3)

jest rozbieżna. Ale jeżeli górna granica jest skończona (k) to mamy liczbę harmoniczną, która oczywiście rośnie wraz ze wzrostem k, ale wzrost ten jest irytująco powolny. Na początku (dla małych k) jeszcze idzie wytrzymać. Na przykład $H_4 = \frac{25}{12} > 2$ , a więc wystarczy ułożyć na sobie cztery karty, aby ta wierzchnia znalazła się całkowicie poza krawędzią stołu. Potem jednak liczby harmoniczne rosną powolutku. Liczba o wskaźniku 1 000 000 (milion!), H_1000000 to skromne 14 z groszami. Śliczny przykład podają autorzy matematyki konkretnej:

Powolny, ale wytrwały robaczek R rozpoczyna wędrówkę od początku metrowej gumowej taśmy i pełznie - z prędkością 1 centymetr na minutę - w kierunku jej końca. Pod koniec każdej minuty równie wytrwały właściciel taśmy W, którego wyłącznym celem w życiu jest pokrzyżowanie planów R, rozciąga taśmę równomiernie o 1 metr. Po jednej minucie R jest odległy o 1 cm od początku swojej drogi i o 99 cm od jej końca. Wówczas W rozciąga taśmę o jeden metr, ale tak, że R zachowuje swoja względną pozycję, czyli 1% od startu i 99% od finiszu. Zatem R znajduje się 2 cm od punktu wyjścia i 198 od celu. Po następnej minucie R osiąga 3 cm taśmy, ma przed sobą 197 cm do przejścia i w tym momencie W rozciąga taśmę. Odpowiednie odległości przyjmują wartości 4,5 i 295,5 cm. I tak dalej....
Na pierwszy rzut oka nie wydaje się w ogóle możliwe aby dzielny robaczek kiedykolwiek dotarł do mety. Ale matematyka jest nieubłagana. Powyższy dość skomplikowany schemat można streścić prosto: w ciągu pierwszej minuty R przebywa jedną setną swojej drogi, w ciągu drugiej - jedną dwusetną, w ciągu trzeciej - jedną trzechsetną. Po n minutach R pokonuje

$\begin{displaymath}\frac{1}{100} \left( \frac 1 1 + \frac 1 2 + \frac 1 3 + \ldots + \frac 1 n\right) = \frac{H_n}{100}. \end{displaymath}$

Wystarczy więc znaleźć wskaźnik n dla którego H_n przekroczy sto. Mimo żółwiego tempa przyrostu liczb harmonicznych wiemy, że prędzej czy później to nastąpi, bo nieskończona suma 3 jest przecież rozbieżna. Warto prześledzić ten sam przykład ale z ,,super-robaczkiem'', który wędruje z prędkością pół metra na minutę. W pierwszej minucie przebywa pół całkowitej drogi, w następnej - jedną czwartą, w trzeciej - jedną szóstą. Po trzech minutach ma przebyte: 1/2 + 1/4 + 1/6 = 11/12 drogi. Ponieważ w czwartej minucie przebyłby $1/2\times1/4 = 1/8$ -mą drogi, to widać że osiągnie metę przed upływem tej czwartej minuty. Rzeczywiście : po trzykrotnym wydłużeniu taśmy o jeden metr jej długość wynosi na początku czwartej minuty cztery metry, z których superrobaczek ma już za sobą 3 i 2/3. Potrzebuje 40 sekund do przebycia pozostałych 33 1/3 centymetrów. Możesz sprawdzić - H₄ >2. Wracając do naszego powolnego robaczka: i on skazany jest na sukces ale .... Aby spróbować oszacować jak wielkie jest n aby $H_n \geq 100$ musimy skorzystać z pewnych skojarzeń, dzięki którym liczby harmoniczne staną się nam nieco bliższe.

Rachunek różnicowy i różniczkowy

Każdy wie, że pochodna funkcji f(x), ${\cal{D}} f(x)$ to granica ilorazu różnicowego

$\begin{displaymath}f'(x) \equiv {\cal{D}} f(x) = \lim_{h\rightarrow 0} \frac {f(x+h) - f(x) }{h}.\end{displaymath}$

(4)

W przypadku kiedy mamy do czynienia ze zmienną dyskretną, a nie ciągłą, odpowiednikiem operatora ${\cal{D}}$ jest operator różnicy $\Delta$ :

$\begin{displaymath}\Delta f(x) = f(x+1) - f(x) .\end{displaymath}$

Byłoby sympatycznie, gdyby taki operator różnicowy posiadał własności zbliżone do operatora ${\cal{D}}$ . Podstawowa własność tego ostatniego to, na przykład,

$\begin{displaymath}{\cal{D}} x^m = mx^{m-1}.\end{displaymath}$

Niestety, analogiczny operator działający na dyskretne zmienne daje coś zupełnie innego:

$\begin{displaymath}\Delta (x^3) = (x+1)^3 - x^3 = 3x^2 + 3x + 1 \neq 3x^2.\end{displaymath}$

Aby operator różnicy zachowywał się wobec potęg dyskretnego x-a podobnie jak jego starszy kolega z dziedziny zmiennej ciągłej musimy ,,przedefiniować'' pojęcie potęgi. Wprowadzamy pojęcie ,,m-tej potęgi ubywającej''

$\begin{displaymath}x^{\underline{m}} = x(x-1)\ldots(x-m+1) \;\; \mbox{\rm całkowite } m \geq 0.\end{displaymath}$

Taka potęga pod działaniem operatora różnicy zachowuje się tak jak trzeba:

$\begin{eqnarray*}\Delta (x^{\underline{m}}) & = & (x+1)^ {\underline{m}} - x^{\u... ...2)(x-m+1)\\ & = & mx(x-1)\ldots (x-m+2) = m x^{\underline{m-1}}.\end{eqnarray*}$

Sprytne, prawda? O rachunku różnicowym można poczytać dużo ciekawych rzeczy w literaturze (matematyce konkretnej). Dla naszych celów wystarczy, jeżeli zdefiniujemy potęgę ubywającą z ujemnym wykładnikiem. Aby to zrobić popatrzmy na sekwencję potęg:

$\begin{eqnarray*}x^{\underline{3}} & = & x(x-1)(x-2) \\ x^{\underline{2}} & = & x(x-1)\\ x^{\underline{1}} & = & x\\ x^{\underline{0}} & = & 1. \end{eqnarray*}$

No tak. Obniżanie stopnia potęgi ubywającej dokonuje się - idąc od góry - dzięki sukcesywnemu dzieleniu: przez x-2, x-1 i x. jeżeli chcemy kontynuować marsz w dół to wydaje się logicznym, aby dzielić $x^{\underline{0}}$ przez analogicznie przyrastające liczby: x+1, x+2, itd. I rzeczywiście:

$\begin{eqnarray*}x^{\underline{-1}} & = & \frac{1}{x+1}, \\ x^{\underline{-2}} ... ...(x+2)}, \\ x^{\underline{-3}} & = & \frac{1}{(x+1)(x+2)(x+3)}, \end{eqnarray*}$

albo ogólnie:

$\begin{displaymath}x^{\underline{-m}} = \frac{1}{(x+1)(x+2)\ldots(x+m)}. \end{displaymath}$

Miało być o liczbach harmonicznych. I będzie! Tak jak w rachunku różniczkowym mamy całki oznaczone, tak w rachunku różnicowym istnieją sumy oznaczone, a związki są analogiczne. Konkretnie, suma ubywających potęg x- a, który to x zmienia się, ze skokiem jednostkowym, od a do b to

$\begin{displaymath}\sum^b_a x^{\underline{m}} =\left. \frac{ x^{\underline{m+1}}}{m+1} \right\vert _a^b \end{displaymath}$

będzie odpowiednikiem naszej poczciwej całki

$\begin{displaymath}\int_a^b x^m dx= \left. \frac{ x^{m+1}}{m+1} \right\vert _a^b .\end{displaymath}$

Powyższe wzory są OK dla $m \neq -1$ . No właśnie. Całka

$\begin{displaymath}\int_a^b x^{-1}dx = \left. \ln x \right\vert _a^b .\end{displaymath}$

(5)

A w rachunku różnicowym? szukamy funkcji f(x) takiej, że

$\begin{displaymath}x^{\underline{-1}} = \frac{1}{x+1} = \Delta f(x) = f(x+1) - f(x).\end{displaymath}$

Komputer zauważy, że taką funkcją jest właśnie liczba harmoniczna, H_x:

$\begin{displaymath}f(x) = \frac 1 1 + \frac 1 2 + \ldots + \frac 1 x = H_x.\end{displaymath}$

Odkryliśmy karty - tajemnicze (?) liczby harmoniczne to odpowiedniki w dziedzinie zmiennej dyskretnej naszych starych, dobrych znajomych logarytmów naturalnych. Pamiętasz - logarytm też należy do rodzinki powolnych funkcji, iloraz $\displaystyle \frac{x^\delta}{\ln x}$ dąży do zera przy $x\rightarrow \infty$ dla każdego $\delta >0$ ! Mówiąc mało precyzyjnie a bardziej obrazowo: dla dużych wartości x zaciera się granica między zmienną ciągłą a dyskretną (jednostkowy krok dyskretny staje się malućki) i wtedy $\ln x$ i H_x to praktycznie jeden diabełek.

Liczby harmoniczne - ciąg dalszy przygód dzielnego robaczka

Prawdę mówiąc nie musieliśmy aż tak uczenie kombinować. To, że liczba harmoniczna jest bliską kuzynką logarytmu naturalnego można łatwo zobaczyć z dwóch podanych niżej rysuneczków. Czerwona krzywa to wykres f(x) = 1/x, a klocki stojące na osi poziomej to kolejne wartości 1/n. Logarytm $\ln n$ można wyrazić przy pomocy całki

$\begin{displaymath}\ln n = \int^n_1 \frac 1 x dx.\end{displaymath}$

Całka ta - pole pod krzywą 1/x - musi być ,,z grubsza'' równa polu poskładanemu z n kolejnych klocków - S_n. Jeżeli klocki stawiać z prawej strony

kolejnych wartości n to widzimy, że pole pod krzywą jest mniejsze od S_n, która to suma to nic innego jak H_n:

$\begin{displaymath}S_n = H_n > \ln n. \end{displaymath}$

Natomiast stawiając n klocków z lewej strony

widzimy, że pole powierzchni n klocków jest mniejsze od sumy: pole powierzchni pierwszego prostokąta (=1) plus pole powierzchni pod krzywą f(x) (cały czas w granicach od 1 do n):

$\begin{displaymath}S_n = H_n < \ln + 1.\end{displaymath}$

Tak więc n-ta liczba harmoniczna jest dość dobrze zlokalizowana:

$\begin{displaymath} \ln n < H_n < \ln +1. \end{displaymath}$

(6)

Możemy zacieśnić pułapkę, w której tkwi H_n. Uogólniona liczba harmoniczna H_n^(p) zdefiniowana jest jako

$\begin{displaymath}H_n^{(p)} = \sum_{k=1}^n \frac{1}{k^p}.\end{displaymath}$

(7)

Sumujemy odwrotności p-tych potęg liczb 1,2,.... p nie musi być całkowite, ale zwykle jest; już dla p>1) powyższa suma ma granicę przy $n\rightarrow \infty$ :

$\begin{displaymath}\lim_{n\rightarrow\infty} H_n^{(p)} = \sum_{k=1}^\infty \frac{1}{k^p} = H_\infty^{(p)} \equiv \zeta(p),\end{displaymath}$

(8)

która nazywa się ,,zetą Riemanna'' .Dla p=2, na przykład,

$\begin{displaymath}\sum_{k=1}^\infty \frac{1}{k^2} = H_\infty^{(2)} = \zeta(2) = \frac{\pi^2}{6}.\end{displaymath}$

(Istnieje pół tuzina standardowych sposobów wykazania tej równości - rachunek reziduów, liczby Bernoulliego, iloczyny nieskończone, itp.) O liczeniu zety Riemanna dla parzystych argumentów jest mowa na stronie o liczbach Bernoulliego. Jeżeli już wprowadzimy uogólnione liczby harmoniczne to związek między ,,zwykłymi'' liczbami harmonicznymi a logarytmem da się przedstawić bardzo zgrabnie. Korzystamy z Taylorowskiego rozwinięcia logarytmu

$\begin{displaymath}\ln(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \ldots + (-1)^{n-1}\frac{x^n}{n} + \ldots, \;\;\; \vert x\vert < 1,\end{displaymath}$

podstawiając nieco inny argument logarytmu:

$\begin{displaymath}\ln \left( \frac{k}{k-1} \right) = -\ln \left(1 - \frac 1 k \... ...k} + \frac{1}{2k^2} + \frac{1}{3k^3} + \frac{1}{4k^4} + \ldots.\end{displaymath}$

Ten szereg jest zbieżny dla k>1 ( |x| = 1/k < 1), a jego lewa strona to $\ln k - \ln(k-1)$ . Sumując obie strony po k od 2 do n mamy

$\begin{eqnarray*}\lefteqn{ \sum_{k=2}^n [\ln k - \ln(k-1)] = \ln n - \ln 1 = \ln... ...) + \frac 1 3 (H_n^{(3)}-1) + \frac 1 4 (H_n^{(4)}-1) + \ldots. \end{eqnarray*}$

Ocierając pot z czoła

$\begin{displaymath}H_n - \ln n = 1 - \frac 1 2 (H_n^{(2)}-1) - \frac 1 3 (H_n^{(3)}-1) - \frac 1 4 (H_n^{(4)}-1) + \ldots,\end{displaymath}$

a w granicy, przy $n\rightarrow \infty$

$\begin{displaymath}\lim_ {n\rightarrow \infty} (H_n - \ln n ) = 1 - \frac 1 2 (\... ...eta^{(3)}-1) \frac 1 4 (\zeta^{(4)}-1) - \ldots \equiv \gamma.\end{displaymath}$

(9)

Stała $\gamma$ to stała Eulera-Mascheroniego. Euler obliczył ją w swoim De progressionibus harmonicis observationes, artykule wydanym w Petersburskich Commentarii academiae scientiarum imperialis Petropolitanae w roku 1734, jako (w przybliżeniu) równą 0,577218. Dzisiaj artyści od asymptotyki liczą rozwinięcia gammy zawierające tysiące cyfr po przecinku i ...gryzą paznokcie z nerwów, bo nikomu nie udało się jeszcze rozstrzygnąć problemu czy ta ,,połówka i ciut'' jest liczbą wymierną czy nie. W każdym razie ograniczenie 6 H_n jest już nieźle uściślone - H_n siedzi w około 58% drogi pomiędzy $\ln n$ a $\ln n +1$ . Jeżeli Cię to jeszcze nie zadowala, to konkretni matematycy podają lepszy wzór

$\begin{displaymath}H_n = \ln n + \gamma + \frac {1}{2n} - \frac{1}{12n^2} + \frac {\epsilon_n} {120n^4}, \;\; 0 < \epsilon_n <1. \end{displaymath}$

(10)

Wracamy do dzielnego robaczka i jego wędrówki, realizowanej na przekór niecnym knowaniom obrzydliwego właściciela gumowej taśmy. Robaczek dopadnie mety gdy H_n przekroczy 100. Z podanych wyżej oszacowań wynika, że będzie to dla n równego z grubsza

$\begin{displaymath}e^{100 - \gamma} \approx e^{99,423}.\end{displaymath}$

Nastąpi to - bagatela - w około 287 decylionów wieków od rozpoczęcia wędrówki. Gumowa taśma rozciągnie się do długości ponad 10²⁷ lat świetlnych, a jej cząsteczki będą bardzo, bardzo daleko od siebie...