Sum of Sequence of Harmonic Numbers/Proof 3

From ProofWiki
Jump to navigation Jump to search

Theorem

$\ds \sum_{k \mathop = 1}^n H_k = \paren {n + 1} H_n - n$

where $H_k$ denotes the $k$th harmonic number.


Proof

Let $\sequence {a_n}$ be the sequence defined as:

$\forall n \in \N_{> 0}: a_n = H_n$

where $H_n$ denotes the $n$th harmonic number.

Let $\map G z$ be the generating function for $\sequence {a_n}$.


From Generating Function for Sequence of Harmonic Numbers:

$\map G z = \dfrac 1 {1 - z} \map \ln {\dfrac 1 {1 - z} }$


Then:

\(\ds \map {G'} z\) \(=\) \(\ds \dfrac 1 {\paren {1 - z}^2} \map \ln {\dfrac 1 {1 - z} } + \dfrac 1 {\paren {1 - z}^2}\) Derivative of Generating Function for Sequence of Harmonic Numbers
\(\ds \) \(=\) \(\ds \dfrac 1 {1 - z} \map G z + \dfrac 1 {\paren {1 - z}^2}\)


From Generating Function for Sequence of Partial Sums of Series, $\dfrac 1 {1 - z} \map G z$ is the generating function for $\sequence {b_n}$ where:

$b_n = \ds \sum_{k \mathop = 0}^n H_k$

and so:

$\dfrac 1 {\paren {1 - z}^2} \map \ln {\dfrac 1 {1 - z} } = \ds \sum_{n \mathop \ge 0} \paren {\sum_{k \mathop = 0}^n H_k} z^n$


From Generating Function for Natural Numbers:

$\dfrac 1 {\paren {1 - z}^2} = \ds \sum_{n \mathop \ge 0} \paren {n + 1} z^n$

That is:

$\map {G'} z = \ds \sum_{n \mathop \ge 0} \paren {\sum_{k \mathop = 0}^n H_k + \paren {n + 1} } z^n$

Now we have:

\(\ds \map {G'} z\) \(=\) \(\ds \map {\dfrac \d {\d z} } {\sum_{n \mathop \ge 0} H_n z^n}\) Derivative of Generating Function for Sequence of Harmonic Numbers
\(\ds \) \(=\) \(\ds \sum_{n \mathop \ge 0} n H_n z^{n - 1}\) Derivative of Power

Equating coefficients of $z^n$ in these two expressions for $\map {G'} z$:

$\ds \sum_{k \mathop = 0}^n H_k + \paren {n + 1} = \paren {n + 1} H_{n + 1}$


\(\ds \sum_{k \mathop = 0}^n H_k + \paren {n + 1}\) \(=\) \(\ds \paren {n + 1} H_{n + 1}\)
\(\ds \) \(=\) \(\ds \paren {n + 1} H_n + \paren {n + 1} \paren {\dfrac 1 {n + 1} }\)
\(\ds \leadsto \ \ \) \(\ds \sum_{k \mathop = 1}^n H_k + n\) \(=\) \(\ds \paren {n + 1} H_n\) $H_k = 0$ when $k = 0$, and simplification

The result follows.

$\blacksquare$


Sources