# How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k}$?

This sum is difficult. How can I compute it, without using calculus?

$$\sum_{k = 1}^n \frac1{k + 1}\binom{n}{k}$$

If someone can explain some technique to do it, I’d appreciate it.
Or advice using a telescopic sum, I think with a telescopic could go, but do not know how to assemble it.

#### Solutions Collecting From Web of "How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k}$?"

\begin{align*}\sum_{k=1}^n \binom{n}{k} \frac{1}{k+1}
= \frac{1}{n+1} \sum_{k=1}^n \binom{n+1}{k+1}
= \frac{2^{n+1} – 1 – (n+1)}{n+1} = \frac{2^{n+1} – n-2}{n+1}.
\end{align*}
The first step follows from the identity $\binom{n}{k} \frac{n+1}{k+1} = \frac{n!}{k! (n-k)!} \frac{n+1}{k+1} = \frac{(n+1)!}{(k+1)! (n-k)!} = \binom{n+1}{k+1}$. The second step uses the fact that $\sum_{k=0}^{n+1} \binom{n+1}{k} = 2^{n+1}$, while noting that $\binom{n+1}{0}$ and $\binom{n+1}{1}$ are not included in the sum.

Here’s a probabilistic approach copied from my answer to a duplicate question. I am reposting here (marked as CW) for the record. We want to show that
$$\frac{1}{2^{n+1}-1} \sum_{j=0}^n \binom{n}{j} \frac{1}{j+1} = \frac{1}{n+1}. \tag{\ast}$$

Consider an experiment where we pick a nonempty subset (“committee”) $S \subseteq \{ 0, 1, 2, \ldots, n \}$ uniformly at random and pick an $x$ uniformly at random from $S$ (the “head” of the committee). Then both sides count the probability that the head is $0$. By symmetry the head is a uniformly random person, so it is $n+1$ with probability $\frac{1}{n+1}$. Therefore, it only remains to justify the left hand side of $(\ast)$.

The probability of the event $E_j$ that $S$ contains $0$ and it also $j$ other people from $\{ 1, 2, \ldots, n\}$ is
$$\frac{1}{2^{n+1}-1} \binom{n}{j}.$$
Conditioned on $E_j$, the probability that the head is $0$ is equal to $\frac{1}{j+1}$. [Finally, conditioned on the event that $0 \notin S$, the probability that the head is $0$ is zero.] Thus, by the law of total probability,
\begin{align*} \Pr[\text{Head is } 0] &= \sum_{j=0}^n \Pr[E_j] \cdot \Pr[\text{Head is } 0 \mid E_j] \\ &= \sum_{j=0}^n \frac{1}{2^{n+1}-1} \binom{n}{j} \cdot \frac{1}{j+1} \end{align*}