Prove $\binom{n}{0} + \frac{1}{2} \binom{n}{1} + \frac{1}{3} \binom{n}{2} + ... + \frac{1}{n+1} \binom{n}{n} = \frac{2^{n + 1} - 1}{n + 1}$.

Question

I have to prove the identity:

$$\binom{n}{0} + \dfrac{1}{2} \binom{n}{1} + \dfrac{1}{3} \binom{n}{2} + ... + \dfrac{1}{n+1} \binom{n}{n} = \dfrac{2^{n + 1} - 1}{n + 1}$$

First thing I tried was to think about a combinatorial proof, but I couldn't interpret the identity in any way that makes sense. So, how should I prove this?

Answer 1

Hint: Integrate the binomial theorem $$(1+x)^n = \sum_{k=0}^n\binom nk x^k$$ from $x=0$ to $x=1$.

Answer 2

We can find the probabilistic interpretation of both sides of the equation: Imagine having $n+1$ people. We then select every possible nonempty subset of them (there are exactly $2^{n+1}-1$ such subsets) and then select one person from it uniformly at random. Both sides are equal to the expected value of the number of times the first person was selected. The RHS iterates over all possible set sizes containing this person and multiplies the number of them by the respective probability. The RHS makes use of the fact that there will be $2^{n+1}-1$ selections in total and that person one is exactly the same as everyone else. Therefore dividing one quantity by the other will yield the answer by virtue of symmetry.