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

Theorem

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

where:

$\dbinom k m$ denotes a binomial coefficient

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

First we note that by Pascal's Rule:

$\dbinom k m = \dbinom {k + 1} {m + 1} - \dbinom k {m + 1}$

Thus:

$\ds \dbinom k m H_k$

$=$

$\ds \dbinom {k + 1} {m + 1} \paren {H_{k + 1} - \dfrac 1 {k + 1} } - \dbinom k {m + 1} H_k$

$\ds \leadsto \ \ $

$\ds \sum_{k \mathop = 1}^n \binom k m H_k$

$=$

$\ds \paren {\binom 2 {m + 1} H_2 - \binom 1 {m + 1} H_1}$

$\ds $

$\, \ds + \, $

$\ds \cdots$

$\ds $

$\, \ds + \, $

$\ds \paren {\binom {n + 1} {m + 1} H_{n + 1} - \binom n {m + 1} H_n}$

$\ds $

$\, \ds - \, $

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

$\ds $

$=$

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

$\ds \leadsto \ \ $

$\ds \sum_{k \mathop = 1}^n \binom k m H_k$

$=$

$\ds \binom {n + 1} {m + 1} \paren {H_{n + 1} - \frac 1 {m + 1} }$

$\blacksquare$