Summation to n of Square of kth Harmonic Number
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{k \mathop = 1}^n {H_k}^2 = \paren {n + 1} {H_n}^2 - \paren {2 n + 1} H_n + 2 n$
where $H_k$ denotes the $k$th harmonic number.
Proof
Consider:
\(\ds \sum_{k \mathop = 1}^{n - 1} \dfrac k {k + 1}\) | \(=\) | \(\ds \sum_{k \mathop = 1}^{n - 1} \dfrac {\paren {k + 1} - 1} {k + 1}\) | factorizing | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 1}^{n - 1} 1 - \sum_{k \mathop = 1}^{n - 1} \dfrac 1 {k + 1}\) | Sum of Summations equals Summation of Sum | |||||||||||
\(\ds \) | \(=\) | \(\ds n - 1 - \sum_{k \mathop = 1}^{n - 1} \dfrac 1 {k + 1}\) | Summation of Unity over Elements | |||||||||||
\(\ds \) | \(=\) | \(\ds n - 1 - \paren {H_n - 1}\) | Harmonic Number and compensate for $\dfrac 1 1$ term | |||||||||||
\(\text {(1)}: \quad\) | \(\ds \) | \(=\) | \(\ds n - H_n\) | simplification |
This page or section has statements made on it that ought to be extracted and proved in a Theorem page. In particular: The above result is worth publishing on its own page as a result in its own right. I'm surprised we don't already have it. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by creating any appropriate Theorem pages that may be needed. To discuss this page in more detail, feel free to use the talk page. |
Using Summation by Parts:
\(\ds \sum_{k \mathop = 1}^n {H_k}^2\) | \(=\) | \(\ds H_n \sum_{k \mathop = 1}^n H_k - \sum_{k \mathop = 1}^{n - 1} \paren {\paren {\sum_{i \mathop = 1}^k {H_i} } \paren {H_{k + 1} - H_k} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds H_n \paren {\paren {n + 1} H_n - n} - \sum_{k \mathop = 1}^{n - 1} \paren {\paren {k + 1} H_k - k} \paren {H_{k + 1} - H_k}\) | Sum of Sequence of Harmonic Numbers twice | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {n + 1} {H_n}^2 - n H_n - \sum_{k \mathop = 1}^{n - 1} \dfrac {\paren {k + 1} H_k - k} {k + 1}\) | $H_{k + 1} - H_k = \dfrac 1 {k+1}$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {n + 1} {H_n}^2 - n H_n - \sum_{k \mathop = 1}^{n - 1} H_k + \sum_{k \mathop = 1}^{n - 1} \dfrac k {k + 1}\) | Sum of Summations equals Summation of Sum | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {n + 1} {H_n}^2 - n H_n - \paren { \sum_{k \mathop = 1}^n H_k - H_n} + \sum_{k \mathop = 1}^{n - 1} \dfrac k {k + 1}\) | increase range of summation and compensate | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {n + 1} {H_n}^2 - n H_n - \paren {\paren {n + 1} H_n - n - H_n } + \sum_{k \mathop = 1}^{n - 1} \dfrac k {k + 1}\) | Sum of Sequence of Harmonic Numbers | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {n + 1} {H_n}^2 - n H_n - \paren {n + 1} H_n + n + H_n + n - H_n\) | $(1)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {n + 1} {H_n}^2 - \paren {2 n + 1} H_n + 2 n\) | simplification |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.7$: Harmonic Numbers: Exercise $15$