Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

How to derive the following equality?

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

share|improve this question

marked as duplicate by Mike Spivey, Srivatsan, J. M., Sivaram Ambikasaran, Byron Schmuland Dec 1 '11 at 4:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Hint: Combine the $j+1$ in the denominator with the $j!$ from $\binom{n}{j}$ to get $(j+1)!$. Then multiply each term by $\frac{n+1}{n+1}$ to get $\binom{n+1}{j+1}$, etc. –  Dilip Sarwate Dec 1 '11 at 3:21

3 Answers 3

up vote 7 down vote accepted

We have $$(1+x)^n = \sum_{j=0}^n \binom{n}{j}x^j.$$

Integrating both sides from $0$ to $x$, we see that

$$\frac{(1+x)^{n+1}-1}{n+1} = \sum_{j=0}^n \binom{n}{j}\frac{x^{j+1}}{j+1}.$$

Putting $x=1$ yields the desired expression.

share|improve this answer
+1. (I guess you could've integrated from $0$ to $1$ instead of integrating till $x$ and plugging in $x=1$. =)) –  Srivatsan Dec 1 '11 at 4:36
Sure! But it's nice to have the general identity when it comes for free, no? :) –  Bruno Joyal Dec 1 '11 at 5:11

Here's a probabilistic approach. 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*} $$

share|improve this answer

Using the identity $$ \binom{n}{j}\frac{n+1}{j+1}=\binom{n+1}{j+1}\tag{1} $$ and summing $$ \begin{align} \sum_{j=0}^n\binom{n}{j}\frac{n+1}{j+1} &=\sum_{j=0}^n\binom{n+1}{j+1}\\ &=2^{n+1}-1\tag{2} \end{align} $$ Dividing by $n+1$ yields $$ \sum_{j=0}^n\binom{n}{j}\frac{1}{j+1}=\frac{2^{n+1}-1}{n+1}\tag{3} $$

share|improve this answer
+1. Neat....... –  Srivatsan Dec 1 '11 at 4:06

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