Prove that $\sum_{r=1}^n \frac 1{r}\binom{n}{r} = \sum_{r=1}^n \frac 1{r}(2^r - 1)$

Prove that $\sum_{r=1}^n \frac 1{r}\binom{n}{r} = \sum_{r=1}^n \frac 1{r}(2^r - 1)$

One thing I have tried is to represent both $\binom{n}{r}$ and $2^r$ as sums of binomial coefficients, i.e. $\sum \binom{i}{r-1}$ and $\sum \binom{r}{i}$ respectively, but it does not seem to be helpful. I have also tried to use binomial identities but I do not see how they can be applied to the problem.

• – lab bhattacharjee Oct 6 '15 at 8:05
• Nice question and nice lead (@labbhattacharjee)! – hypergeometric Oct 7 '15 at 10:35

$$\sum_{r=1}^n \frac{1}{r}\binom{n}{r}=\int_{0}^1\sum_{r=1}^n\binom{n}{r}x^{r-1}dx=\int_{0}^1\frac{(1+x)^r-1}{x}dx\\=\int_{0}^1\sum_{r=1}^n (1+x)^{r-1}dx\\=\sum_{r=1}^n \frac{2^r-1}{r}$$
\begin{align} \sum_{r=1}^n\frac 1r\binom nr &=\sum_{r=1}^n\frac 1r\sum_{k=r}^n\binom kr-\binom{k-1}r \qquad\qquad\qquad\text{(*)}\\ &=\sum_{r=1}^n\frac 1r\sum_{k=r}^n\binom {k-1}{r-1}\\ &=\sum_{r=1}^n\sum_{k=r}^n\frac1k\binom kr\\ &=\sum_{k=1}^n\frac 1k\sum_{r=1}^k\binom kr\\ &=\sum_{k=1}^n\frac 1k(2^k-1)\\ &=\sum_{r=1}^n\frac 1r(2^r-1)\qquad\blacksquare \end{align} * by "untelescoping" $\binom nr$ and noting that $\binom {r-1}r=0$.