Exercise 2089Combinatorics › Binomial coefficientsOlympiadAdded 3 Nov 2026

A challenging binomial sum

#binomial#sum#generating function

Statement

Compute $\sum_{k=0}^{n}\binom{n}{k}\frac{1}{k+1}$ .

Hint

$\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\binom{n+1}{k+1}$ .

Show solutionHide solution

Rewrite. $\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\binom{n+1}{k+1}$ .

Sum. $\sum_{k=0}^{n}\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\sum_{k=0}^{n}\binom{n+1}{k+1}=\frac{1}{n+1}(2^{n+1}-1)$ .

Conclusion. $\sum_{k=0}^{n}\frac{\binom{n}{k}}{k+1}=\frac{2^{n+1}-1}{n+1}$ .