Showing a sum is positiveFinding Binomial expansion of a radicalSimplify the Expression $sum _ k=0 ^ n binomnki^k3^k-n $Alternative combinatorial proof for $sumlimits_r=0^nbinomnrbinomm+rn=sumlimits_r=0^nbinomnrbinommr2^r$Proof by induction, binomial coefficientApproximating a binomial sum over a simplexHow to expand $sqrtx^6+1$ using Maclaurin's seriesSum of $m choose j$ multiplied by $2^2^j$How to show that $sumlimits_k=0^n (-1)^ktfrac nchoosek x+kchoosek = fracxx+n$Finite sum with inverse binomialShowing an alternating sum is positive
Why does AES have exactly 10 rounds for a 128-bit key, 12 for 192 bits and 14 for a 256-bit key size?
How to explain what's wrong with this application of the chain rule?
Is there a way to have vectors outlined in a Vector Plot?
Why do Radio Buttons not fill the entire outer circle?
The Digit Triangles
Can a stoichiometric mixture of oxygen and methane exist as a liquid at standard pressure and some (low) temperature?
How can ping know if my host is down
What's the name of the logical fallacy where a debater extends a statement far beyond the original statement to make it true?
How would you translate "more" for use as an interface button?
Quoting Keynes in a lecture
What kind of floor tile is this?
Why is the Sun approximated as a black body at ~ 5800 K?
Is there any evidence that Cleopatra and Caesarion considered fleeing to India to escape the Romans?
How can I write humor as character trait?
The IT department bottlenecks progress, how should I handle this?
Did the UK lift the requirement for registering SIM cards?
How much theory knowledge is actually used while playing?
Plot of a tornado shape like surface
Giving feedback to someone without sounding prejudiced
How do I fix the group tension caused by my character stealing and possibly killing without provocation?
How could a planet have erratic days?
Stack Interview Code methods made from class Node and Smart Pointers
Why does this expression simplify as such?
Can you use Vicious Mockery to win an argument or gain favours?
Showing a sum is positive
Finding Binomial expansion of a radicalSimplify the Expression $sum _ k=0 ^ n binomnki^k3^k-n $Alternative combinatorial proof for $sumlimits_r=0^nbinomnrbinomm+rn=sumlimits_r=0^nbinomnrbinommr2^r$Proof by induction, binomial coefficientApproximating a binomial sum over a simplexHow to expand $sqrtx^6+1$ using Maclaurin's seriesSum of $m choose j$ multiplied by $2^2^j$How to show that $sumlimits_k=0^n (-1)^ktfrac nchoosek x+kchoosek = fracxx+n$Finite sum with inverse binomialShowing an alternating sum is positive
$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
$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
$endgroup$
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
1 hour ago
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
$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 1 hour ago
Hitendra Kumar
asked 1 hour ago
Hitendra KumarHitendra Kumar
656
656
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
1 hour ago
add a comment |
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
1 hour ago
1
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
1 hour ago
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
1 hour ago
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.
$endgroup$
$begingroup$
Thanks,I got it.
$endgroup$
– Hitendra Kumar
1 hour ago
$begingroup$
You're welcome!
$endgroup$
– Stefan Lafon
1 hour ago
$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
1 hour ago
2
$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
59 mins ago
$begingroup$
Thanks for responding.Got it.
$endgroup$
– NoChance
49 mins ago
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?
$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
1 hour ago
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 $n$. 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.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3157740%2fshowing-a-sum-is-positive%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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.
$endgroup$
$begingroup$
Thanks,I got it.
$endgroup$
– Hitendra Kumar
1 hour ago
$begingroup$
You're welcome!
$endgroup$
– Stefan Lafon
1 hour ago
$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
1 hour ago
2
$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
59 mins ago
$begingroup$
Thanks for responding.Got it.
$endgroup$
– NoChance
49 mins ago
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.
$endgroup$
$begingroup$
Thanks,I got it.
$endgroup$
– Hitendra Kumar
1 hour ago
$begingroup$
You're welcome!
$endgroup$
– Stefan Lafon
1 hour ago
$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
1 hour ago
2
$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
59 mins ago
$begingroup$
Thanks for responding.Got it.
$endgroup$
– NoChance
49 mins ago
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.
$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 1 hour ago
Stefan LafonStefan Lafon
3,02019
3,02019
$begingroup$
Thanks,I got it.
$endgroup$
– Hitendra Kumar
1 hour ago
$begingroup$
You're welcome!
$endgroup$
– Stefan Lafon
1 hour ago
$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
1 hour ago
2
$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
59 mins ago
$begingroup$
Thanks for responding.Got it.
$endgroup$
– NoChance
49 mins ago
add a comment |
$begingroup$
Thanks,I got it.
$endgroup$
– Hitendra Kumar
1 hour ago
$begingroup$
You're welcome!
$endgroup$
– Stefan Lafon
1 hour ago
$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
1 hour ago
2
$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
59 mins ago
$begingroup$
Thanks for responding.Got it.
$endgroup$
– NoChance
49 mins ago
$begingroup$
Thanks,I got it.
$endgroup$
– Hitendra Kumar
1 hour ago
$begingroup$
Thanks,I got it.
$endgroup$
– Hitendra Kumar
1 hour ago
$begingroup$
You're welcome!
$endgroup$
– Stefan Lafon
1 hour ago
$begingroup$
You're welcome!
$endgroup$
– Stefan Lafon
1 hour ago
$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
1 hour ago
$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
1 hour ago
2
2
$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
59 mins ago
$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
59 mins ago
$begingroup$
Thanks for responding.Got it.
$endgroup$
– NoChance
49 mins ago
$begingroup$
Thanks for responding.Got it.
$endgroup$
– NoChance
49 mins ago
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?
$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
1 hour ago
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?
$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
1 hour ago
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?
$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 1 hour ago
David G. StorkDavid G. Stork
11.1k41432
11.1k41432
$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
1 hour ago
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
1 hour ago
$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
1 hour ago
$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
1 hour ago
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 $n$. 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.
$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 $n$. 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.
$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 $n$. 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.
$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 $n$. 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 30 mins ago
Mike EarnestMike Earnest
25.5k22151
25.5k22151
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3157740%2fshowing-a-sum-is-positive%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Have you tried using induction on $n$ for example?
$endgroup$
– Minus One-Twelfth
1 hour ago