10
$\begingroup$

Calculate $$A={1\over {n\choose 0}}+ {1\over {n\choose 1}}+ ...+{1\over {n\choose n}}$$

and

$$B={1\over {n\choose 0}}- {1\over {n\choose 1}}+ ...+{(-1)^n\over {n\choose n}}$$


My idea for $A$ is some probabilistic reasoning. Color the sets $$\{\}, \{1\}, \{1,2\}, \{1,2,3\},...\{1,2,...,n\}$$ and ask our self what is the probability that I choose colored set among all sets. Clearly this is exactly ${n+1\over 2^n}$ and on the other side it is $A$:

probability that I take empty set is ${1\over {n\choose 0}}$,

probability that I take colored set with 1 element is ${1\over {n\choose 1}}$

probability that I take colored set with 2 elements is ${1\over {n\choose 2}}$

and so on ...

So $A ={n+1\over 2^n}$. But I have no idea how to attack $B$.

$\endgroup$
  • 4
    $\begingroup$ ${n\choose k}={n\choose n-k}$, so when $n$ is odd and we have $(-1)^k\neq (-1)^{n-k}$, lots of terms cancel. Could that help? $\endgroup$ – Mastrem Oct 18 '17 at 19:05
  • 1
    $\begingroup$ The first sum is certainly larger than $2$ for $n>1$. So I don't see how that sum could directly represent some probability. And furthermore, $A$ can't equal $\frac{n+1}{2^n}$ as you conclude, because it is typically smaller than $2$. $\endgroup$ – alex.jordan Oct 18 '17 at 19:08
  • $\begingroup$ So I blow it, do you have an idea how to fix it? $\endgroup$ – Aqua Oct 18 '17 at 19:16
  • 1
    $\begingroup$ A Google search for "sum of reciprocals of binomial coefficients" turns up many relevant results. There seems to be no closed form, but a number of equivalent sums and a recurrence are there. $\endgroup$ – marty cohen Oct 18 '17 at 19:17
12
$\begingroup$

A good moment for exploiting the beauty of Euler's Beta function. $$\begin{eqnarray*}\sum_{k=0}^{n}\frac{(-1)^k}{\binom{n}{k}}&=&(n+1)\sum_{k=0}^{n}(-1)^k \frac{\Gamma(k+1)\Gamma(n-k+1)}{\Gamma(n+2)}\\&=&(n+1)\sum_{k=0}^{n}(-1)^kB(k+1,n-k+1)\\&=&(n+1)\int_{0}^{1}\sum_{k=0}^{n}(-1)^k (1-x)^k x^{n-k}\,dx\\&=&(n+1)\int_{0}^{1}(-1)^n(1-x)^{n+1}+x^{n+1}\,dx\\&=&\color{blue}{\frac{n+1}{n+2}((-1)^n+1)}.\end{eqnarray*}$$

$\endgroup$
  • $\begingroup$ I believe this is nice result, but I don't know anything about Beta function. Actually it is a problem from some contest for secondary school students.Do you have any idea to solve it with more elementary method? $\endgroup$ – Aqua Oct 18 '17 at 19:14
  • 1
    $\begingroup$ @JohnWatson: for a more elementary solution, combine induction, symmetry and what you already know about the sum with constant signs. $\endgroup$ – Jack D'Aurizio Oct 18 '17 at 19:15
  • $\begingroup$ I seem to recall this is a quite famous problem, solved by Pascal himself. It is kind of strange it has been used in a contest, but not that unsual after all. $\endgroup$ – Jack D'Aurizio Oct 18 '17 at 19:17
4
$\begingroup$

I found the solution, though it is not mine. Write $${n\choose k}' := {(-1)^k\over {n\choose k}} $$

Then it is easy to prove $${n\choose k+1}'-{n\choose k}' =-{n+1\over n}{n-1\choose k}'$$ so we have: \begin{eqnarray} B&=&\sum _{k=0}^n {n\choose k}' \\&=&-{n+1\over n+2} \sum _{k=0}^n \Big[ {n+1\choose k+1}'-{n+1\choose k}'\Big] \\ &=& -{n+1\over n+2}\Big[ {n+1\choose n+1}'-{n+1\choose 0}'\Big] \\ &=& -{n+1\over n+2}\big( (-1)^{n+1}-1\big)\\ &=& {n+1\over n+2}\big( (-1)^n+1\big)\\ \end{eqnarray}

$\endgroup$

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.