Showing $sum_k=0^n n choose kfrac(-1)^kn+k+1$ is positive The Next CEO of Stack OverflowIs there a closed form for the sum $sum_k=2^N N choose k frack-1k$?Evaluating a sum with binomial coefficients: $sum_k=1^n n choose k frac1k^r a^k b^n-k$Binomial Coefficients Proof: $sum_k=0^n n choose k ^2 = 2n choose n$.Sums $sum_k = 0^n k^t n choose k$ where $t$ is a positive integerNice formula for $sum_m=0^n2mchoose m2(n-m)choose n-m$?How to expand $sqrtx^6+1$ using Maclaurin's seriesSum of $m choose j$ multiplied by $2^2^j$Evaluate $sum_j=0^n(-1)^n+jnchoose jn+jchoose jfrac1(j+1)^2$Prove that $sum_k=0^n (-1)^kfrac nchoosek xchoosek ychoosek = frac y-xchoosen ychoosen$How to show that $sumlimits_k=0^n (-1)^ktfrac nchoosek x+kchoosek = fracxx+n$
Calculate the Mean mean of two numbers
"Eavesdropping" vs "Listen in on"
Why did the Drakh emissary look so blurred in S04:E11 "Lines of Communication"?
My boss doesn't want me to have a side project
Is it "common practice in Fourier transform spectroscopy to multiply the measured interferogram by an apodizing function"? If so, why?
Direct Implications Between USA and UK in Event of No-Deal Brexit
Can you teleport closer to a creature you are Frightened of?
How can the PCs determine if an item is a phylactery?
How can I separate the number from the unit in argument?
Are British MPs missing the point, with these 'Indicative Votes'?
Can a PhD from a non-TU9 German university become a professor in a TU9 university?
Compensation for working overtime on Saturdays
Calculating discount not working
Another proof that dividing by 0 does not exist -- is it right?
Why does sin(x) - sin(y) equal this?
Can I cast Thunderwave and be at the center of its bottom face, but not be affected by it?
How to compactly explain secondary and tertiary characters without resorting to stereotypes?
What happens if you break a law in another country outside of that country?
Is it possible to make a 9x9 table fit within the default margins?
pgfplots: How to draw a tangent graph below two others?
Prodigo = pro + ago?
Upgrading From a 9 Speed Sora Derailleur?
Does the Idaho Potato Commission associate potato skins with healthy eating?
Could a dragon use hot air to help it take off?
Showing $sum_k=0^n n choose kfrac(-1)^kn+k+1$ is positive
The Next CEO of Stack OverflowIs there a closed form for the sum $sum_k=2^N N choose k frack-1k$?Evaluating a sum with binomial coefficients: $sum_k=1^n n choose k frac1k^r a^k b^n-k$Binomial Coefficients Proof: $sum_k=0^n n choose k ^2 = 2n choose n$.Sums $sum_k = 0^n k^t n choose k$ where $t$ is a positive integerNice formula for $sum_m=0^n2mchoose m2(n-m)choose n-m$?How to expand $sqrtx^6+1$ using Maclaurin's seriesSum of $m choose j$ multiplied by $2^2^j$Evaluate $sum_j=0^n(-1)^n+jnchoose jn+jchoose jfrac1(j+1)^2$Prove that $sum_k=0^n (-1)^kfrac nchoosek xchoosek ychoosek = frac y-xchoosen ychoosen$How to show that $sumlimits_k=0^n (-1)^ktfrac nchoosek x+kchoosek = fracxx+n$
$begingroup$
Show that the sum$$sum_k=0^n n choose kfrac(-1)^kn+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.
combinatorics summation binomial-coefficients binomial-ideals
edited Mar 22 at 9:46
YuiTo Cheng
2,1863937
asked Mar 22 at 4:28
Hitendra KumarHitendra Kumar
756
$endgroup$
add a comment |
$begingroup$
Show that the sum$$sum_k=0^n n choose kfrac(-1)^kn+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.
combinatorics summation binomial-coefficients binomial-ideals
edited Mar 22 at 9:46
YuiTo Cheng
2,1863937
asked Mar 22 at 4:28
Hitendra KumarHitendra Kumar
756
$endgroup$
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
Mar 22 at 4:29
add a comment |
$begingroup$
Show that the sum$$sum_k=0^n n choose kfrac(-1)^kn+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.
combinatorics summation binomial-coefficients binomial-ideals
edited Mar 22 at 9:46
YuiTo Cheng
2,1863937
asked Mar 22 at 4:28
Hitendra KumarHitendra Kumar
756
$endgroup$
Show that the sum$$sum_k=0^n n choose kfrac(-1)^kn+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.
combinatorics summation binomial-coefficients binomial-ideals
combinatorics summation binomial-coefficients binomial-ideals
edited Mar 22 at 9:46
YuiTo Cheng
2,1863937
asked Mar 22 at 4:28
Hitendra KumarHitendra Kumar
756
edited Mar 22 at 9:46
YuiTo Cheng
2,1863937
asked Mar 22 at 4:28
Hitendra KumarHitendra Kumar
756
edited Mar 22 at 9:46
YuiTo Cheng
2,1863937
edited Mar 22 at 9:46
YuiTo Cheng
2,1863937
edited Mar 22 at 9:46
YuiTo Cheng
2,1863937
2,1863937
asked Mar 22 at 4:28
Hitendra KumarHitendra Kumar
756
asked Mar 22 at 4:28
Hitendra KumarHitendra Kumar
756
asked Mar 22 at 4:28
Hitendra KumarHitendra Kumar
756
756
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
Mar 22 at 4:29
add a comment |
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
Mar 22 at 4:29
1
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
Mar 22 at 4:29
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
Mar 22 at 4:29
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Direct proof:
$$beginsplit
sum_k=0^n nchoose kfrac(-1)^kn+k+1 &=sum_k=0^n nchoose k(-1)^kint_0^1 x^n+kdx\
&=int_0^1x^nsum_k=0^n nchoose k(-x)^kdx\
&=int_0^1x^n(1-x)^ndx
endsplit$$
The latter is clearly a positive number.
answered Mar 22 at 4:46
Stefan LafonStefan Lafon
3,005212
$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
add a comment |
$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?
answered Mar 22 at 4:35
David G. StorkDavid G. Stork
11.6k41533
$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
add a comment |
$begingroup$
We can specifically prove that
$$
boxedsum_k=0^n n choose kfrac(-1)^kn+k+1=left((2n+1)binom2nnright)^-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 $binomn1frac1n+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.
answered Mar 22 at 5:47
Mike EarnestMike Earnest
26.5k22151
$endgroup$
add a comment |
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?
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Direct proof:
$$beginsplit
sum_k=0^n nchoose kfrac(-1)^kn+k+1 &=sum_k=0^n nchoose k(-1)^kint_0^1 x^n+kdx\
&=int_0^1x^nsum_k=0^n nchoose k(-x)^kdx\
&=int_0^1x^n(1-x)^ndx
endsplit$$
The latter is clearly a positive number.
answered Mar 22 at 4:46
Stefan LafonStefan Lafon
3,005212
$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
add a comment |
$begingroup$
Direct proof:
$$beginsplit
sum_k=0^n nchoose kfrac(-1)^kn+k+1 &=sum_k=0^n nchoose k(-1)^kint_0^1 x^n+kdx\
&=int_0^1x^nsum_k=0^n nchoose k(-x)^kdx\
&=int_0^1x^n(1-x)^ndx
endsplit$$
The latter is clearly a positive number.
answered Mar 22 at 4:46
Stefan LafonStefan Lafon
3,005212
$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
add a comment |
$begingroup$
Direct proof:
$$beginsplit
sum_k=0^n nchoose kfrac(-1)^kn+k+1 &=sum_k=0^n nchoose k(-1)^kint_0^1 x^n+kdx\
&=int_0^1x^nsum_k=0^n nchoose k(-x)^kdx\
&=int_0^1x^n(1-x)^ndx
endsplit$$
The latter is clearly a positive number.
answered Mar 22 at 4:46
Stefan LafonStefan Lafon
3,005212
$endgroup$
Direct proof:
$$beginsplit
sum_k=0^n nchoose kfrac(-1)^kn+k+1 &=sum_k=0^n nchoose k(-1)^kint_0^1 x^n+kdx\
&=int_0^1x^nsum_k=0^n nchoose k(-x)^kdx\
&=int_0^1x^n(1-x)^ndx
endsplit$$
The latter is clearly a positive number.
answered Mar 22 at 4:46
Stefan LafonStefan Lafon
3,005212
answered Mar 22 at 4:46
Stefan LafonStefan Lafon
3,005212
answered Mar 22 at 4:46
Stefan LafonStefan Lafon
3,005212
answered Mar 22 at 4:46
Stefan LafonStefan Lafon
3,005212
3,005212
$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
add a comment |
$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
$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
$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
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
$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
add a comment |
$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?
answered Mar 22 at 4:35
David G. StorkDavid G. Stork
11.6k41533
$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
add a comment |
$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?
answered Mar 22 at 4:35
David G. StorkDavid G. Stork
11.6k41533
$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
add a comment |
$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?
answered Mar 22 at 4:35
David G. StorkDavid G. Stork
11.6k41533
$endgroup$
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?
answered Mar 22 at 4:35
David G. StorkDavid G. Stork
11.6k41533
answered Mar 22 at 4:35
David G. StorkDavid G. Stork
11.6k41533
answered Mar 22 at 4:35
David G. StorkDavid G. Stork
11.6k41533
answered Mar 22 at 4:35
David G. StorkDavid G. Stork
11.6k41533
11.6k41533
$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
add a comment |
$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
$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
$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
add a comment |
$begingroup$
We can specifically prove that
$$
boxedsum_k=0^n n choose kfrac(-1)^kn+k+1=left((2n+1)binom2nnright)^-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 $binomn1frac1n+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.
answered Mar 22 at 5:47
Mike EarnestMike Earnest
26.5k22151
$endgroup$
add a comment |
$begingroup$
We can specifically prove that
$$
boxedsum_k=0^n n choose kfrac(-1)^kn+k+1=left((2n+1)binom2nnright)^-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 $binomn1frac1n+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.
answered Mar 22 at 5:47
Mike EarnestMike Earnest
26.5k22151
$endgroup$
add a comment |
$begingroup$
We can specifically prove that
$$
boxedsum_k=0^n n choose kfrac(-1)^kn+k+1=left((2n+1)binom2nnright)^-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 $binomn1frac1n+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.
answered Mar 22 at 5:47
Mike EarnestMike Earnest
26.5k22151
$endgroup$
We can specifically prove that
$$
boxedsum_k=0^n n choose kfrac(-1)^kn+k+1=left((2n+1)binom2nnright)^-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 $binomn1frac1n+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.
answered Mar 22 at 5:47
Mike EarnestMike Earnest
26.5k22151
edited Mar 22 at 6:32
answered Mar 22 at 5:47
Mike EarnestMike Earnest
26.5k22151
answered Mar 22 at 5:47
Mike EarnestMike Earnest
26.5k22151
answered Mar 22 at 5:47
Mike EarnestMike Earnest
26.5k22151
26.5k22151
add a comment |
add a comment |
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?
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
Mar 22 at 4:29