Combinatorial Proof (Argument) The 2019 Stack Overflow Developer Survey Results Are InCombinatorial proof for two identitiesCombinatorial ArgumentHow to prove it by means of a combinatorial argument?(A combinatorial exercise)Combinatorial proof of an identitycombinatorial argument and by induction proofAlgebraic proof of combinatorial identityChu-Vandermonde-like combinatorial identityProve combinatorial Identity using a combinatorial argument.Combinatorial Proof, Binomial CoefficientsCombinatorial proof of Negative Binomial Identity
Can we generate random numbers using irrational numbers like π and e?
What is the most efficient way to store a numeric range?
Kerning for subscripts of sigma?
If a sorcerer casts the Banishment spell on a PC while in Avernus, does the PC return to their home plane?
What could be the right powersource for 15 seconds lifespan disposable giant chainsaw?
I am an eight letter word. What am I?
Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?
Why does the nucleus not repel itself?
What do hard-Brexiteers want with respect to the Irish border?
How do PCB vias affect signal quality?
What is this business jet?
What is the light source in the black hole images?
What does Linus Torvalds mean when he says that Git "never ever" tracks a file?
What is the meaning of Triage in Cybersec world?
Is it safe to harvest rainwater that fell on solar panels?
Falsification in Math vs Science
How to type a long/em dash `—`
ODD NUMBER in Cognitive Linguistics of WILLIAM CROFT and D. ALAN CRUSE
Why isn't the circumferential light around the M87 black hole's event horizon symmetric?
Accepted by European university, rejected by all American ones I applied to? Possible reasons?
How can I define good in a religion that claims no moral authority?
Why are there uneven bright areas in this photo of black hole?
Are spiders unable to hurt humans, especially very small spiders?
Loose spokes after only a few rides
Combinatorial Proof (Argument)
The 2019 Stack Overflow Developer Survey Results Are InCombinatorial proof for two identitiesCombinatorial ArgumentHow to prove it by means of a combinatorial argument?(A combinatorial exercise)Combinatorial proof of an identitycombinatorial argument and by induction proofAlgebraic proof of combinatorial identityChu-Vandermonde-like combinatorial identityProve combinatorial Identity using a combinatorial argument.Combinatorial Proof, Binomial CoefficientsCombinatorial proof of Negative Binomial Identity
$begingroup$
Give a combinatorial proof for:
$$sum_j=0^k binomnj = sum_j=0^k binomn-1-jk-j 2^j$$
combinatorics binomial-coefficients binomial-theorem
edited Mar 24 at 5:07
Rhys Hughes
7,0501630
asked Mar 24 at 4:56
user569748user569748
523
$endgroup$
add a comment |
$begingroup$
Give a combinatorial proof for:
$$sum_j=0^k binomnj = sum_j=0^k binomn-1-jk-j 2^j$$
combinatorics binomial-coefficients binomial-theorem
edited Mar 24 at 5:07
Rhys Hughes
7,0501630
asked Mar 24 at 4:56
user569748user569748
523
$endgroup$
1
$begingroup$
Hi and welcome to MSE! I want to remind you that it is generally preferred you include context when asking a question here (which can include: where this problem came from, your own attempts, and a specific idea as to where you're stuck) - it also lets us help you better! As is, your question is little more than an isolated problem, and thus likely to get a lot of downvotes and closed. Feel free to edit the context into your post though! Here's some useful links: asking a good question and a MathJax reference to format your work.
$endgroup$
– Eevee Trainer
Mar 24 at 4:57
$begingroup$
Welcome to MSE. Eevee covered most of the points you should follow, your Mathjax was good to see but you forgot the $$ at either end, but I would also suggest you tell us what a "combinatorial proof" is, in addition to what you've tried on the question.
$endgroup$
– Rhys Hughes
Mar 24 at 5:13
add a comment |
$begingroup$
Give a combinatorial proof for:
$$sum_j=0^k binomnj = sum_j=0^k binomn-1-jk-j 2^j$$
combinatorics binomial-coefficients binomial-theorem
edited Mar 24 at 5:07
Rhys Hughes
7,0501630
asked Mar 24 at 4:56
user569748user569748
523
$endgroup$
Give a combinatorial proof for:
$$sum_j=0^k binomnj = sum_j=0^k binomn-1-jk-j 2^j$$
combinatorics binomial-coefficients binomial-theorem
combinatorics binomial-coefficients binomial-theorem
edited Mar 24 at 5:07
Rhys Hughes
7,0501630
asked Mar 24 at 4:56
user569748user569748
523
edited Mar 24 at 5:07
Rhys Hughes
7,0501630
asked Mar 24 at 4:56
user569748user569748
523
edited Mar 24 at 5:07
Rhys Hughes
7,0501630
edited Mar 24 at 5:07
Rhys Hughes
7,0501630
edited Mar 24 at 5:07
Rhys Hughes
7,0501630
7,0501630
asked Mar 24 at 4:56
user569748user569748
523
asked Mar 24 at 4:56
user569748user569748
523
asked Mar 24 at 4:56
user569748user569748
523
523
1
$begingroup$
Hi and welcome to MSE! I want to remind you that it is generally preferred you include context when asking a question here (which can include: where this problem came from, your own attempts, and a specific idea as to where you're stuck) - it also lets us help you better! As is, your question is little more than an isolated problem, and thus likely to get a lot of downvotes and closed. Feel free to edit the context into your post though! Here's some useful links: asking a good question and a MathJax reference to format your work.
$endgroup$
– Eevee Trainer
Mar 24 at 4:57
$begingroup$
Welcome to MSE. Eevee covered most of the points you should follow, your Mathjax was good to see but you forgot the $$ at either end, but I would also suggest you tell us what a "combinatorial proof" is, in addition to what you've tried on the question.
$endgroup$
– Rhys Hughes
Mar 24 at 5:13
add a comment |
1
$begingroup$
Hi and welcome to MSE! I want to remind you that it is generally preferred you include context when asking a question here (which can include: where this problem came from, your own attempts, and a specific idea as to where you're stuck) - it also lets us help you better! As is, your question is little more than an isolated problem, and thus likely to get a lot of downvotes and closed. Feel free to edit the context into your post though! Here's some useful links: asking a good question and a MathJax reference to format your work.
$endgroup$
– Eevee Trainer
Mar 24 at 4:57
$begingroup$
Welcome to MSE. Eevee covered most of the points you should follow, your Mathjax was good to see but you forgot the $$ at either end, but I would also suggest you tell us what a "combinatorial proof" is, in addition to what you've tried on the question.
$endgroup$
– Rhys Hughes
Mar 24 at 5:13
1
1
$begingroup$
Hi and welcome to MSE! I want to remind you that it is generally preferred you include context when asking a question here (which can include: where this problem came from, your own attempts, and a specific idea as to where you're stuck) - it also lets us help you better! As is, your question is little more than an isolated problem, and thus likely to get a lot of downvotes and closed. Feel free to edit the context into your post though! Here's some useful links: asking a good question and a MathJax reference to format your work.
$endgroup$
– Eevee Trainer
Mar 24 at 4:57
$begingroup$
Hi and welcome to MSE! I want to remind you that it is generally preferred you include context when asking a question here (which can include: where this problem came from, your own attempts, and a specific idea as to where you're stuck) - it also lets us help you better! As is, your question is little more than an isolated problem, and thus likely to get a lot of downvotes and closed. Feel free to edit the context into your post though! Here's some useful links: asking a good question and a MathJax reference to format your work.
$endgroup$
– Eevee Trainer
Mar 24 at 4:57
$begingroup$
Welcome to MSE. Eevee covered most of the points you should follow, your Mathjax was good to see but you forgot the $$ at either end, but I would also suggest you tell us what a "combinatorial proof" is, in addition to what you've tried on the question.
$endgroup$
– Rhys Hughes
Mar 24 at 5:13
$begingroup$
Welcome to MSE. Eevee covered most of the points you should follow, your Mathjax was good to see but you forgot the $$ at either end, but I would also suggest you tell us what a "combinatorial proof" is, in addition to what you've tried on the question.
$endgroup$
– Rhys Hughes
Mar 24 at 5:13
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $S_m$ be a set of all sequences $(a_1, a_2, ldots , a_m)$ such that $a_iin0,1$ for all $iin1,2ldots, m$. It's clear that $|S_n|=2^n$. Then, it's easy to see that $binomnj$ equals to number of the elements $(a_1, a_2, ldots, a_n)$ of a set $S_n$ such that among $a_i$ there exactly $j$ 'ones'. Therefore, sum $sumlimits_j=0^k binomnj$ equals to number of elements of $S_n$ that has at most $k$ 'ones'. Denote set of elements of $S_n$ that has at most $k$ 'ones' as $T$. We proved that $|T|=sumlimits_j=0^k binomnj$.
On the other hand, we can count number of elements of $T$ in the following way. Every sequence $overlinea=(a_1,a_2,ldots, a_n)in T$ has at least $n-k$ 'zeros'. For every sequence $overlineain T$ let $s(overlinea)$ be the position of $n-k$-th 'zero' in sequence $overlinea$. Note that $n-kleq s(overlinea)leq n$ for all $overlineain T$. Now, consider number of sequences $overlinea$ in $T$ such that $s(overlinea)=n-j$ for sime fixed $0leq jleq k$. Among $a_1, a_2, ldots, a_s(overlinea)-1$ there exactly $n-k-1$ 'zeros', so there $binoms(overlinea)-1n-k-1=binomn-j-1n-k-1=binomn-j-1k-j$ options for subsequence $a_1, a_2, ldots, a_s(overlinea)-1$. Then, $a_s(overlinea)=1$ and for $i>s(overlinea)$ term $a_iin 0,1$ (there no condition for it), so there $2^j$ options for subsequence $a_s(overlinea), ldots, a_n$. Hence, for fixed $0leq jleq k$ there exactly $binomn-1-jk-j 2^j$ elements $overlinea$ in $T$ with property $s(overlinea)=n-j$. Thus, $|T|=sumlimits_j=0^kbinomn-1-jk-j 2^j$. Since $|T|=sumlimits_j=0^k binomnj$ we obtain that
$$
sum_j=0^k binomnj=sum_j=0^kbinomn-1-jk-j 2^j,
$$
as desired.
answered Mar 24 at 8:14
richrowrichrow
50819
$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%2f3160111%2fcombinatorial-proof-argument%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $S_m$ be a set of all sequences $(a_1, a_2, ldots , a_m)$ such that $a_iin0,1$ for all $iin1,2ldots, m$. It's clear that $|S_n|=2^n$. Then, it's easy to see that $binomnj$ equals to number of the elements $(a_1, a_2, ldots, a_n)$ of a set $S_n$ such that among $a_i$ there exactly $j$ 'ones'. Therefore, sum $sumlimits_j=0^k binomnj$ equals to number of elements of $S_n$ that has at most $k$ 'ones'. Denote set of elements of $S_n$ that has at most $k$ 'ones' as $T$. We proved that $|T|=sumlimits_j=0^k binomnj$.
On the other hand, we can count number of elements of $T$ in the following way. Every sequence $overlinea=(a_1,a_2,ldots, a_n)in T$ has at least $n-k$ 'zeros'. For every sequence $overlineain T$ let $s(overlinea)$ be the position of $n-k$-th 'zero' in sequence $overlinea$. Note that $n-kleq s(overlinea)leq n$ for all $overlineain T$. Now, consider number of sequences $overlinea$ in $T$ such that $s(overlinea)=n-j$ for sime fixed $0leq jleq k$. Among $a_1, a_2, ldots, a_s(overlinea)-1$ there exactly $n-k-1$ 'zeros', so there $binoms(overlinea)-1n-k-1=binomn-j-1n-k-1=binomn-j-1k-j$ options for subsequence $a_1, a_2, ldots, a_s(overlinea)-1$. Then, $a_s(overlinea)=1$ and for $i>s(overlinea)$ term $a_iin 0,1$ (there no condition for it), so there $2^j$ options for subsequence $a_s(overlinea), ldots, a_n$. Hence, for fixed $0leq jleq k$ there exactly $binomn-1-jk-j 2^j$ elements $overlinea$ in $T$ with property $s(overlinea)=n-j$. Thus, $|T|=sumlimits_j=0^kbinomn-1-jk-j 2^j$. Since $|T|=sumlimits_j=0^k binomnj$ we obtain that
$$
sum_j=0^k binomnj=sum_j=0^kbinomn-1-jk-j 2^j,
$$
as desired.
answered Mar 24 at 8:14
richrowrichrow
50819
$endgroup$
add a comment |
$begingroup$
Let $S_m$ be a set of all sequences $(a_1, a_2, ldots , a_m)$ such that $a_iin0,1$ for all $iin1,2ldots, m$. It's clear that $|S_n|=2^n$. Then, it's easy to see that $binomnj$ equals to number of the elements $(a_1, a_2, ldots, a_n)$ of a set $S_n$ such that among $a_i$ there exactly $j$ 'ones'. Therefore, sum $sumlimits_j=0^k binomnj$ equals to number of elements of $S_n$ that has at most $k$ 'ones'. Denote set of elements of $S_n$ that has at most $k$ 'ones' as $T$. We proved that $|T|=sumlimits_j=0^k binomnj$.
On the other hand, we can count number of elements of $T$ in the following way. Every sequence $overlinea=(a_1,a_2,ldots, a_n)in T$ has at least $n-k$ 'zeros'. For every sequence $overlineain T$ let $s(overlinea)$ be the position of $n-k$-th 'zero' in sequence $overlinea$. Note that $n-kleq s(overlinea)leq n$ for all $overlineain T$. Now, consider number of sequences $overlinea$ in $T$ such that $s(overlinea)=n-j$ for sime fixed $0leq jleq k$. Among $a_1, a_2, ldots, a_s(overlinea)-1$ there exactly $n-k-1$ 'zeros', so there $binoms(overlinea)-1n-k-1=binomn-j-1n-k-1=binomn-j-1k-j$ options for subsequence $a_1, a_2, ldots, a_s(overlinea)-1$. Then, $a_s(overlinea)=1$ and for $i>s(overlinea)$ term $a_iin 0,1$ (there no condition for it), so there $2^j$ options for subsequence $a_s(overlinea), ldots, a_n$. Hence, for fixed $0leq jleq k$ there exactly $binomn-1-jk-j 2^j$ elements $overlinea$ in $T$ with property $s(overlinea)=n-j$. Thus, $|T|=sumlimits_j=0^kbinomn-1-jk-j 2^j$. Since $|T|=sumlimits_j=0^k binomnj$ we obtain that
$$
sum_j=0^k binomnj=sum_j=0^kbinomn-1-jk-j 2^j,
$$
as desired.
answered Mar 24 at 8:14
richrowrichrow
50819
$endgroup$
add a comment |
$begingroup$
Let $S_m$ be a set of all sequences $(a_1, a_2, ldots , a_m)$ such that $a_iin0,1$ for all $iin1,2ldots, m$. It's clear that $|S_n|=2^n$. Then, it's easy to see that $binomnj$ equals to number of the elements $(a_1, a_2, ldots, a_n)$ of a set $S_n$ such that among $a_i$ there exactly $j$ 'ones'. Therefore, sum $sumlimits_j=0^k binomnj$ equals to number of elements of $S_n$ that has at most $k$ 'ones'. Denote set of elements of $S_n$ that has at most $k$ 'ones' as $T$. We proved that $|T|=sumlimits_j=0^k binomnj$.
On the other hand, we can count number of elements of $T$ in the following way. Every sequence $overlinea=(a_1,a_2,ldots, a_n)in T$ has at least $n-k$ 'zeros'. For every sequence $overlineain T$ let $s(overlinea)$ be the position of $n-k$-th 'zero' in sequence $overlinea$. Note that $n-kleq s(overlinea)leq n$ for all $overlineain T$. Now, consider number of sequences $overlinea$ in $T$ such that $s(overlinea)=n-j$ for sime fixed $0leq jleq k$. Among $a_1, a_2, ldots, a_s(overlinea)-1$ there exactly $n-k-1$ 'zeros', so there $binoms(overlinea)-1n-k-1=binomn-j-1n-k-1=binomn-j-1k-j$ options for subsequence $a_1, a_2, ldots, a_s(overlinea)-1$. Then, $a_s(overlinea)=1$ and for $i>s(overlinea)$ term $a_iin 0,1$ (there no condition for it), so there $2^j$ options for subsequence $a_s(overlinea), ldots, a_n$. Hence, for fixed $0leq jleq k$ there exactly $binomn-1-jk-j 2^j$ elements $overlinea$ in $T$ with property $s(overlinea)=n-j$. Thus, $|T|=sumlimits_j=0^kbinomn-1-jk-j 2^j$. Since $|T|=sumlimits_j=0^k binomnj$ we obtain that
$$
sum_j=0^k binomnj=sum_j=0^kbinomn-1-jk-j 2^j,
$$
as desired.
answered Mar 24 at 8:14
richrowrichrow
50819
$endgroup$
Let $S_m$ be a set of all sequences $(a_1, a_2, ldots , a_m)$ such that $a_iin0,1$ for all $iin1,2ldots, m$. It's clear that $|S_n|=2^n$. Then, it's easy to see that $binomnj$ equals to number of the elements $(a_1, a_2, ldots, a_n)$ of a set $S_n$ such that among $a_i$ there exactly $j$ 'ones'. Therefore, sum $sumlimits_j=0^k binomnj$ equals to number of elements of $S_n$ that has at most $k$ 'ones'. Denote set of elements of $S_n$ that has at most $k$ 'ones' as $T$. We proved that $|T|=sumlimits_j=0^k binomnj$.
On the other hand, we can count number of elements of $T$ in the following way. Every sequence $overlinea=(a_1,a_2,ldots, a_n)in T$ has at least $n-k$ 'zeros'. For every sequence $overlineain T$ let $s(overlinea)$ be the position of $n-k$-th 'zero' in sequence $overlinea$. Note that $n-kleq s(overlinea)leq n$ for all $overlineain T$. Now, consider number of sequences $overlinea$ in $T$ such that $s(overlinea)=n-j$ for sime fixed $0leq jleq k$. Among $a_1, a_2, ldots, a_s(overlinea)-1$ there exactly $n-k-1$ 'zeros', so there $binoms(overlinea)-1n-k-1=binomn-j-1n-k-1=binomn-j-1k-j$ options for subsequence $a_1, a_2, ldots, a_s(overlinea)-1$. Then, $a_s(overlinea)=1$ and for $i>s(overlinea)$ term $a_iin 0,1$ (there no condition for it), so there $2^j$ options for subsequence $a_s(overlinea), ldots, a_n$. Hence, for fixed $0leq jleq k$ there exactly $binomn-1-jk-j 2^j$ elements $overlinea$ in $T$ with property $s(overlinea)=n-j$. Thus, $|T|=sumlimits_j=0^kbinomn-1-jk-j 2^j$. Since $|T|=sumlimits_j=0^k binomnj$ we obtain that
$$
sum_j=0^k binomnj=sum_j=0^kbinomn-1-jk-j 2^j,
$$
as desired.
answered Mar 24 at 8:14
richrowrichrow
50819
answered Mar 24 at 8:14
richrowrichrow
50819
answered Mar 24 at 8:14
richrowrichrow
50819
answered Mar 24 at 8:14
richrowrichrow
50819
50819
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%2f3160111%2fcombinatorial-proof-argument%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$
Hi and welcome to MSE! I want to remind you that it is generally preferred you include context when asking a question here (which can include: where this problem came from, your own attempts, and a specific idea as to where you're stuck) - it also lets us help you better! As is, your question is little more than an isolated problem, and thus likely to get a lot of downvotes and closed. Feel free to edit the context into your post though! Here's some useful links: asking a good question and a MathJax reference to format your work.
$endgroup$
– Eevee Trainer
Mar 24 at 4:57
$begingroup$
Welcome to MSE. Eevee covered most of the points you should follow, your Mathjax was good to see but you forgot the $$ at either end, but I would also suggest you tell us what a "combinatorial proof" is, in addition to what you've tried on the question.
$endgroup$
– Rhys Hughes
Mar 24 at 5:13