5
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

$$\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}$$

$\endgroup$
7
$\begingroup$

Solution without using calculus:

$$\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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.