6

Provide a combinatorial proof of the identity $$\sum_{k = 0}^n \frac{1}{k + 1}{n \choose k} = \frac{2^{n + 1} - 1}{n + 1}$$

My Proof

I was able to demonstrate combinatorially that \begin{align} 2^{n + 1} - 1 &= \sum_{k = 0}^n {{n + 1} \choose k} \tag{1}\\ (n + 1){n \choose k} &= (k + 1){{n + 1} \choose {k + 1}} \tag{2} \end{align}

Following from $(1)$ and $(2)$, the theorem to be proven is equivalent to \begin{multline*} \sum_{k = 0}^n \frac{n + 1}{k + 1}{n \choose k} = 2^{n + 1} - 1 \iff \sum_{k = 0}^n {{n + 1} \choose {k + 1}} = \sum_{k = 0}^n {{n + 1} \choose k}\\ \iff {{n+1} \choose {n + 1}} + \sum_{k = 1}^n {{n + 1} \choose k} = {{n + 1} \choose 0} + \sum_{k = 1}^n {{n + 1} \choose k} \iff \sum_{k = 1}^n {{n + 1} \choose k} = \sum_{k = 1}^n {{n + 1} \choose k} \end{multline*}

It hence holds that $$\boxed{\sum_{k = 0}^n \frac{1}{k + 1}{n \choose k} = \frac{2^{n + 1} - 1}{n + 1}}$$

My Question

Is there combinatorial proof that involves no algebraic manipulation whatsoever? I ask this because I am particularly interested in how we can interpret division combinatorially.

  • How about a double-counting proof that evaluates the right-hand side as an integral that computes the mean of a function of a random variable? – J.G. Aug 08 '22 at 10:37
  • @J.G. Ooooh, that sounds interesting! –  Aug 08 '22 at 10:38

1 Answers1

4

Here's the not-quite-what-was-asked-for proof I hinted at in the comments.

I come upon $n$ people, and they are each assigned, with probability $\frac12$, to play with me a game that can have an arbitrary positive number of players; I might even play alone. If a $k$-set of them are my opponents, there are $k+1$ players. The game is simple: we each get independent $U(0,\,1)$ numbers, and the biggest wins. My chance of winning is $\frac{1}{k+1}$, and your identity's left-hand side is $2^n$ times my mean chance of winning across all potential sets of opponents.

Let's calculate my chance of winning another way, to check it's $2^{-n}\frac{2^{n+1}-1}{n+1}$. If my random number is $x$, a given person fails to beat me (possibly due to not even playing) with chance $\frac12(1+x)$, so my chance of winning is $2^{-n}\int_0^1(1+x)^ndx$, which is as desired.

J.G.
  • 115,835