Showing $\sum_{k=0}^{n} {n \choose k}\frac{{(-1)}^k}{n+k+1}$ is positive

Question

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.

Answer 1

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?

Answer 2

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.

Answer 3

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.