Prove that
This proof showcases the power of OGF, ordinary generating function. Starting with the Talyer series expansion at around zero:
In other words, the ordinary generating function (OGF) of the sequence (
1,1,⋯,1), which are the coefficients of
∑N≥0zN, is
11−z.
Differentiating both sides of OGF1:
|
1(1−z)2=∑N≥0NzN−1=∑N≥1NzN−11(1−z)2=∑N≥0(N+1)zNre-index |
Integrating both sides of
OGF1:
|
−ln(1−z)=ln11−z=∑N≥0zN+1N+1ln11−z=∑N≥11NzNre-index |
which means
ln(11−z) is the OGF for the harmonic sequence (
1,12,⋯,1N).
Recall, in general, if
A(z)=∑k≥0akzk is the OGF of (
a0,a1,⋯,ak,⋯), then
11−zA(z) is the OGF of (
a0,a0+a1,a0+a1+a2,⋯). So
|
11−zln11−z=∑N≥1(∑1≤k≤N1N)zN=∑N≥1HNzN1(1−z)2ln11−z=∑N≥1(∑1≤k≤NHk)zN applying 11−z again![zN]1(1−z)2ln11−z=∑1≤k≤NHkextract coefficient of zN |
But recall from above
|
1(1−z)2ln11−z=(∑N≥0(N+1)zN)(∑k≥11kzk)=∑N≥0∑k≥1(N+1)1kzN+k=∑N≥k∑k≥1(N−k+1)1kzNre-index=∑N≥1(∑1≤k≤N(N+1−k)1k)zN=∑N≥1(∑1≤k≤N(1k(N+1)−1))zN=∑N≥1(HN(N+1)−N)zN[zN]1(1−z)2ln11−z=HN(N+1)−Nextract coefficient of zN∴ |
Now
|
\begin{aligned}
H_{N+1} &= H_N + \frac{1}{N+1} \\
H_N &= H_{N+1} - \frac{1}{N+1} \\
\sum_{1 \le k \le N} H_k &= (H_{N+1} - \frac{1}{N+1}) (N + 1) - N \\
&= (N + 1) H_{N+1} - 1 - N = (N + 1) H_{N+1} - (N+1) \\
\sum_{1 \le k \le N} H_k &= (N+1)(H_{N+1} - 1) \\
\end{aligned}
|
\Box
Source: Analysis of Algorithm
# posted by rot13(Unafba Pune) @ 3:21 PM
