I need the combinatorial proof for the following identity

Question

$$ \sum_{r=0}^{n}\frac{\binom{n}{r}}{r+1}=\frac{2^{n+1}-1}{n+1} $$

I know how to write combinatorial proof when the radicals are being added or multiplied. I want to know how to do the same in the case of division of radicals.

Answer 1

Hint 1: the LHS is $$\sum_{r=0}^n \binom{n}{r} \int_0^1 x^r\mathrm d x = \int_0^1(1+x)^n\mathrm dx$$

---

Hint 2: If you want a pure combinatorial proof. How many non empty subsets there in a set of cardinality $n+1$?

• $\sum_{r=0}^{n} \binom{n+1}{r+1}$

• $2^{n+1} -1$

Now rearrange terms and you will find your identity

Answer 2

We will use the lemma:

$$(n+1)\binom nr=(r+1)\binom{n+1}{r+1}\tag1$$

This can be proved combinatorially counting in two ways the number of committees of $r+1$ people from $n+1$ people, with one committee member selected as chairperson.

The left side of $(1)$ corresponds to choosing the chair first, and then choosing the $r$ other members, while the right side chooses the $r+1$ members and then selects the chair from those $r+1.$

From $(1),$ you get:

$$\frac{n+1}{r+1}\binom nr=\binom{n+1}{r+1}$$

And thus $$(n+1)\sum_{r=0}^n\frac1{r+1}\binom nr=\sum_{r=0}^n\binom {n+1}{r+1}\tag2$$

But the right side of $(2)$ counts the non-empty subsets of a set of size $n+1,$ which is $2^{n+1}-1.$

Then we divide by $n+1.$

It is not really possible to prove directly the original formula combinatorially because the values are not always integers. You have to find a common denominator to turn it into an integer equation, but luckily, here, one common denominator is $n+1.$

Answer 3

Here is a purely combinatorial argument without rearrangement.

Suppose you draw a permutation $\pi$ uniformly at random from $[n+1]=\{1, 2, \ldots, n+1\}$. You are interested in the expected number $\mu$ of subsets of $S\subseteq [n]$ such that $n+1$ is after all the elements of $S$ in the permutation $\pi$.

For example, if $n=3$, and the permutation drawn is $\pi=2143$, then the subsets are $\{2\}, \{1\}, \{2,1\}, \{\}$ for a total of $4$.

How do we compute $\mu$? One way is to use Linearity of expectation on the size of the subsets $S$:

$$\mu = \sum_{r=0}^{n} \sum_{S\subseteq [n], |S|=r} \Pr[n+1 \text{ is after }S \text{ in }\pi] = \sum_{r=0}^{n} \sum_{S\subseteq[n], |S|=r}\frac{1}{r+1}$$ This is because if we focus on the $r$ elements of $S$ and $n+1$, the probability the random permutation has $n+1$ after $S$ is $1/(r+1)$. But this summation simplifies to

$$\sum_{r=0}^n \frac{{n \choose r}}{r+1}$$

Now we calculate $\mu$ a different way. Consider the location of $n+1$ in $\pi$. It lands in location $\ell, 1\leq \ell \leq n+1$ with probability $1/(n+1)$. If it falls in location $\ell$, then only the $2^{\ell-1}$ subsets generated by the elements before $\ell$ count in the expectation. So again, the expectation is

$$\mu = \sum_{\ell=1}^{n+1}2^{\ell-1}\frac{1}{n+1} = \frac{2^{n+1}-1}{n+1}$$

Answer 4

Set Up

My class has $n+1$ students including myself. During the break, we do the following fun activity:

• A non-empty subset of students are selected
• At random, one of the selected students is slapped

The activity is repeated, each with a different non-empty subset and it's stopped only when there is no more distinct non-empty subset left. What is the expected value of slaps I get?

Left Hand Side

The number of subsets with $r+1$ people including myself is $\binom{n}{r}$ and in this group my chance of getting slapped is $\frac{1}{r+1}$. Therefore the expected number of slaps I get is given by the left hand side:

$$ \sum_{r=0}^{n}\frac{1}{r+1}\binom{n}{r} $$

Right Hand Side

There are a total of $2^{n+1}-1$ non-empty subsets and each students must have the same expected number of slaps. Therefore my (and others') expected number of slaps is given by the right hand side:

$$ \frac{1}{n+1}\left(2^{n+1}-1\right) $$

Conclusion

Since LHS and RHS calculate the same thing, they must be equal i.e.

$$ \sum_{r=0}^{n}\frac{1}{r+1}\binom{n}{r} = \frac{1}{n+1}\left(2^{n+1}-1\right) $$

Remarks

When I encounter fractions and want to use combinatorial proof, the first thing that comes to my mind is probability or expected value.