Sum of Sequence of Harmonic Numbers

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 1

\(\ds \sum_{k \mathop = 1}^n H_k\) \(=\) \(\ds \sum_{k \mathop = 1}^n \paren {\sum_{j \mathop = 1}^k \frac 1 j}\) Definition of Harmonic Numbers
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 1}^n \paren {\sum_{k \mathop = j}^n \frac 1 j}\) Summation of i from 1 to n of Summation of j from 1 to i
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 1}^n \paren {\paren {1 + 1 + \cdots + 1} + \paren {\dfrac 1 2 + \dfrac 1 2 + \cdots + \dfrac 1 2} + \cdots + \paren {\dfrac 1 n} }\) $n$ copies of $1$, $\paren {n - 1}$ copies of $\dfrac 1 2$, $\paren {n - 2}$ copies of $\dfrac 1 3$
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 1}^n \paren {n + 1 - j} \times \frac 1 j\)
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 1}^n \frac {n + 1 - j} j\)
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 1}^n \frac {n + 1} j - \sum_{j \mathop = 1}^n \frac j j\) Linear Combination of Convergent Series
\(\ds \) \(=\) \(\ds \paren {n + 1} H_n - n\) Linear Combination of Convergent Series and Definition of Harmonic Numbers

$\blacksquare$


Proof 2

From Sum over k to n of k Choose m by kth Harmonic Number:

$\ds \sum_{k \mathop = 1}^n \binom k m H_k = \binom {n + 1} {m + 1} \paren {H_{n + 1} - \frac 1 {m + 1} }$

Setting $m = 0$:

\(\ds \sum_{k \mathop = 1}^n \binom k 0 H_k\) \(=\) \(\ds \binom {n + 1} {0 + 1} \paren {H_{n + 1} - \frac 1 {0 + 1} }\)
\(\ds \leadsto \ \ \) \(\ds \sum_{j \mathop = 1}^n H_k\) \(=\) \(\ds \paren {n + 1} \paren {H_{n + 1} - 1}\) Binomial Coefficient with $0$, Binomial Coefficient with $1$
\(\ds \) \(=\) \(\ds \paren {n + 1} \paren {H_n + \frac 1 {n + 1} - 1}\) Definition of Harmonic Number
\(\ds \) \(=\) \(\ds \paren {n + 1} H_n + \paren {n + 1} \frac 1 {n + 1} - \paren {n + 1} 1\)
\(\ds \) \(=\) \(\ds \paren {n + 1} H_n + 1 - \paren {n + 1}\)
\(\ds \) \(=\) \(\ds \paren {n + 1} H_n - n\)

$\blacksquare$


Proof 3

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

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_of_Sequence_of_Harmonic_Numbers&oldid=542184"