6
$\begingroup$

Show that the sum$$\sum_{k=0}^{n} {n \choose k}\frac{{(-1)}^k}{n+k+1}$$ is a positive rational number.

It is easy to show that it is a rational number. But I am having trouble showing that this expression is positive. It might be some binomial expansion that I could not get.

$\endgroup$
  • 1
    $\begingroup$ Have you tried using induction on $n$ for example? $\endgroup$ – Minus One-Twelfth Mar 22 at 4:29
16
$\begingroup$

Direct proof: $$\begin{split} \sum_{k=0}^{n} {n\choose k}\frac{{(-1)}^k}{n+k+1} &=\sum_{k=0}^{n} {n\choose k}(-1)^k\int_0^1 x^{n+k}dx\\ &=\int_0^1x^n\sum_{k=0}^{n} {n\choose k}(-x)^kdx\\ &=\int_0^1x^n(1-x)^ndx \end{split}$$ The latter is clearly a positive number.

$\endgroup$
  • $\begingroup$ How did you conclude that the sum is a limited integral? Do you know where can I find more on this on-line? Thanks. $\endgroup$ – NoChance Mar 22 at 5:13
  • 4
    $\begingroup$ It's a "known trick" that $\frac 1 {p+1} = \int_0^1x^pdx$. Then I noticed that the sum looked almost like that of the binomial theorem. $\endgroup$ – Stefan Lafon Mar 22 at 5:18
7
$\begingroup$

When $k=0$ the term is positive. When $k=1$ the term is negative BUT SMALLER (in absolute value) THAN THE $k=0$ TERM.

When $k=2$ the term is positive. When $k=3$ the term is negative BUT SMALLER (in absolute value) THAN THE $k=2$ TERM.

.....

Get it?

$\endgroup$
  • $\begingroup$ sorry, I did not write question correctly. Now, I have corrected that. By looking at your answer I realized my mistake. Thanks $\endgroup$ – Hitendra Kumar Mar 22 at 4:42
7
$\begingroup$

We can specifically prove that $$ \boxed{\sum_{k=0}^{n} {n \choose k}\frac{{(-1)}^k}{n+k+1}=\left((2n+1)\binom{2n}n\right)^{-1}} $$ To see this, shuffle a deck of $2n+1$ cards numbered $1$ to $2n+1$. Consider this:

What is the probability that card number $n+1$ is in the middle of the deck, and cards numbered $1$ to $n$ are below it?

The easy answer is the fraction on the RHS. The LHS can be interpreted as an application of the principle of inclusion exclusion. Namely, we first take the probability that card number of $n+1$ is the lowest of the cards numbered $n+1,n+2,\dots,2n+1$. This is the $k=0$ term. From this, for each $i=1,\dots,n$, we subtract the probability that $n+1$ is the lowest of the list $i,n+1,n+2,\dots,2n+1$. This is a bad event, because we want $n+1$ to be above $i$. Doing this for each $i$, we subtract $\binom{n}1\frac{1}{n+2}$. We then must add back in the doubly subtracted events, subtract the triple intersections, and so on, eventually ending with the alternating sum on the left.

$\endgroup$

protected by Community Mar 22 at 10:13

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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