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.

  • $\begingroup$ Note that $n \choose r$ doesn't depend on $k$. Or did you mean $\sum_{k=1}^n \frac{1}{k+1} {n \choose k}$? $\endgroup$ – Robert Israel Sep 20 '11 at 16:40
  • $\begingroup$ @kuch nahi: I think you should undelete your answer. It does use calculus and so doesn't help the OP, but it would be interesting to others reading the question. Maybe you could just add a note at the top of your answer to that effect. $\endgroup$ – Mike Spivey Sep 20 '11 at 16:57

\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.

  • 4
    $\begingroup$ +1 for nice answer. I corrected a typo in the upper bound of the sum. $\endgroup$ – Sasha Sep 20 '11 at 17:59

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*} $$

  • $\begingroup$ I don't think it's necessary that this be community wiki. It's a good answer. $\endgroup$ – Mike Spivey Dec 1 '11 at 4:02
  • 1
    $\begingroup$ @Mike I posted this as CW because it's just a copy of the other answer. =) $\endgroup$ – Srivatsan Dec 1 '11 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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