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.

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.

share|improve this question
    
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}$? –  Robert Israel Sep 20 '11 at 16:40
3  
Be aware that people will be not super eager to help someone with a 0% accept rate. –  user12205 Sep 20 '11 at 16:41
    
@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. –  Mike Spivey Sep 20 '11 at 16:57
add comment

2 Answers 2

up vote 23 down vote accepted

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

share|improve this answer
3  
+1 for nice answer. I corrected a typo in the upper bound of the sum. –  Sasha Sep 20 '11 at 17:59
add comment

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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