Prove that

\[ \begin{aligned} \sum_{1 \le k \le N} H_k = (N+1)(H_{N+1} - 1) \\ \end{aligned} \]

This proof showcases the power of OGF, ordinary generating function. Starting with the Talyer series expansion at around zero:

\[ \begin{aligned} OGF_1 = \frac{1}{1 - z} = \sum_{N \ge 0}z^N \end{aligned} \]

In other words, the ordinary generating function (OGF) of the sequence (\(1, 1, \cdots, 1\)), which are the coefficients of \(\displaystyle \sum_{N \ge 0}z^N\), is \(\displaystyle \frac{1}{1 - z}\).

Differentiating both sides of \(OGF_1\):

\[ \begin{aligned} \frac{1}{(1 - z)^2} &= \sum_{N \ge 0}N z^{N-1} = \sum_{N \ge 1}N z^{N-1}\\ \color{teal}{\frac{1}{(1 - z)^2}} &\color{teal}{= \sum_{N \ge 0}(N+1)z^N} & \text{re-index} \\ \end{aligned} \]

Integrating both sides of \(OGF_1\):

\[ \begin{aligned} - \ln (1-z) &= \ln \frac{1}{1 - z} = \sum_{N \ge 0} \frac{z^{N+1}}{N+1} \\ \color{teal}{\ln \frac{1}{1 - z}} &\color{teal}{= \sum_{N \ge 1} \frac{1}{N} z^N} & \text{re-index} \\ \end{aligned} \]

which means \(\displaystyle \ln (\frac{1}{1 - z})\) is the OGF for the harmonic sequence (\(\displaystyle 1, \frac{1}{2}, \cdots, \frac{1}{N}\)). Recall, in general, if \(\displaystyle A(z) = \sum_{k \ge 0} a_k z^k \) is the OGF of (\(a_0, a_1, \cdots, a_k, \cdots\)), then \(\displaystyle \frac{1}{1-z} A(z) \) is the OGF of (\(a_0, a_0+a_1, a_0+a_1+a_2, \cdots \)). So

\[ \begin{aligned} \frac{1}{1-z} \ln \frac{1}{1 - z} &= \sum_{N \ge 1} \big( \sum_{1 \le k \le N} \frac{1}{N} \big) z^N = \sum_{N \ge 1} H_N z^N \\ \frac{1}{(1-z)^2} \ln \frac{1}{1 - z} &= \sum_{N \ge 1} \big( \color{blue}{\sum_{1 \le k \le N} H_k} \big) z^N & \text{ applying } \frac{1}{1-z} \text{ again!} \\ \color{blue}{[z^N] \frac{1}{(1-z)^2} \ln \frac{1}{1 - z}} &\color{blue}{= \sum_{1 \le k \le N} H_k} & \text{extract coefficient of } z^N \\ \end{aligned} \]

But recall from above

\[ \begin{aligned} \color{teal}{\frac{1}{(1 - z)^2} \ln \frac{1}{1 - z}} &\color{teal}{= \big(\sum_{N \ge 0}(N+1)z^N\big) \big(\sum_{k \ge 1} \frac{1}{k} z^k\big)} \\ &= \sum_{N \ge 0} \sum_{k \ge 1} (N+1) \frac{1}{k} z^{N+k} \\ &= \sum_{N \ge k} \sum_{k \ge 1} (N-k + 1) \frac{1}{k} z^{N} & \text{re-index} \\ &= \sum_{N \ge 1} \big( \sum_{1 \le k \le N} (N+1-k) \frac{1}{k} \big) z^{N} \\ &= \sum_{N \ge 1} \big( \sum_{1 \le k \le N} (\frac{1}{k}(N + 1) - 1) \big) z^{N} \\ &= \sum_{N \ge 1} \big( \color{blue}{H_N (N + 1) - N} \big) z^{N} \\ \color{blue}{[z^N] \frac{1}{(1 - z)^2} \ln \frac{1}{1 - z}} &\color{blue}{= H_N (N + 1) - N} & \text{extract coefficient of } z^N \\ \therefore \sum_{1 \le k \le N} H_k &= H_N (N + 1) - N \\ \end{aligned} \]

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