Sum of Sequence of Harmonic Numbers/Proof 2
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
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$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.7$: Harmonic Numbers: $(8)$