5
$\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
  • 1
    $\begingroup$ Have you tried using induction on $n$ for example? $\endgroup$ Mar 22, 2019 at 4:29

3 Answers 3

19
$\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$
2
  • $\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, 2019 at 5:13
  • 8
    $\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$ Mar 22, 2019 at 5:18
8
$\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$
1
  • $\begingroup$ sorry, I did not write question correctly. Now, I have corrected that. By looking at your answer I realized my mistake. Thanks $\endgroup$ Mar 22, 2019 at 4:42
5
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .