Mixing
Combinatorial proof of ${n choose 1} + {n choose 3} +cdots = {n choose 0} + {n choose 2}+cdots$
$begingroup$
Give a combinatorial proof of
$${n choose 1} + {n choose 3} +cdots = {n choose 0} + {n choose 2}+cdots$$
In first of all, I know how to proof directly. We move all terms to left hand side of equation. And we get $(1-1)^n = 0^n = 0$, and we are done. Also I saw here several topics about this, but it never were about the combinatorial proof.
I want this prove combinatorial. I have no idea of question, which will be correctly answered from both side of equation. Thank you for all hints.
combinatorial-proofs
asked Jan 28 at 19:11
KapurKapur
606
$endgroup$
add a comment |
$begingroup$
Give a combinatorial proof of
$${n choose 1} + {n choose 3} +cdots = {n choose 0} + {n choose 2}+cdots$$
In first of all, I know how to proof directly. We move all terms to left hand side of equation. And we get $(1-1)^n = 0^n = 0$, and we are done. Also I saw here several topics about this, but it never were about the combinatorial proof.
I want this prove combinatorial. I have no idea of question, which will be correctly answered from both side of equation. Thank you for all hints.
combinatorial-proofs
asked Jan 28 at 19:11
KapurKapur
606
$endgroup$
2
$begingroup$
Let $[n]={1,2,ldots,n}$. The left hand side counts subsets of $[n]$ with an odd number of elements, while the right hand side counts subsets of $[n]$ with an even number of elements. How could you go from one to the other and back?
$endgroup$
– Kevin Long
Jan 28 at 19:13
add a comment |
$begingroup$
Give a combinatorial proof of
$${n choose 1} + {n choose 3} +cdots = {n choose 0} + {n choose 2}+cdots$$
In first of all, I know how to proof directly. We move all terms to left hand side of equation. And we get $(1-1)^n = 0^n = 0$, and we are done. Also I saw here several topics about this, but it never were about the combinatorial proof.
I want this prove combinatorial. I have no idea of question, which will be correctly answered from both side of equation. Thank you for all hints.
combinatorial-proofs
asked Jan 28 at 19:11
KapurKapur
606
$endgroup$
Give a combinatorial proof of
$${n choose 1} + {n choose 3} +cdots = {n choose 0} + {n choose 2}+cdots$$
In first of all, I know how to proof directly. We move all terms to left hand side of equation. And we get $(1-1)^n = 0^n = 0$, and we are done. Also I saw here several topics about this, but it never were about the combinatorial proof.
I want this prove combinatorial. I have no idea of question, which will be correctly answered from both side of equation. Thank you for all hints.
combinatorial-proofs
combinatorial-proofs
asked Jan 28 at 19:11
KapurKapur
606
asked Jan 28 at 19:11
KapurKapur
606
asked Jan 28 at 19:11
KapurKapur
606
asked Jan 28 at 19:11
KapurKapur
606
asked Jan 28 at 19:11
KapurKapur
606
606
2
$begingroup$
Let $[n]={1,2,ldots,n}$. The left hand side counts subsets of $[n]$ with an odd number of elements, while the right hand side counts subsets of $[n]$ with an even number of elements. How could you go from one to the other and back?
$endgroup$
– Kevin Long
Jan 28 at 19:13
add a comment |
2
$begingroup$
Let $[n]={1,2,ldots,n}$. The left hand side counts subsets of $[n]$ with an odd number of elements, while the right hand side counts subsets of $[n]$ with an even number of elements. How could you go from one to the other and back?
$endgroup$
– Kevin Long
Jan 28 at 19:13
2
2
$begingroup$
Let $[n]={1,2,ldots,n}$. The left hand side counts subsets of $[n]$ with an odd number of elements, while the right hand side counts subsets of $[n]$ with an even number of elements. How could you go from one to the other and back?
$endgroup$
– Kevin Long
Jan 28 at 19:13
$begingroup$
Let $[n]={1,2,ldots,n}$. The left hand side counts subsets of $[n]$ with an odd number of elements, while the right hand side counts subsets of $[n]$ with an even number of elements. How could you go from one to the other and back?
$endgroup$
– Kevin Long
Jan 28 at 19:13
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let's call a set even if it has an even number of elements and odd if it has an odd number of elements. As @KevinLong stated in the comments, the LHS counts the number of odd subsets of $n$ elements and the RHS counts the number of even subsets of $n$ elements.
Let's call the $n$ element set we're dividing up $N$. Fix some arbitrary element $x in N$. We can partition the set of subsets of $N$ by whether they include $x$. For any subset of $N$ which includes $x$, there is exactly one subset of $N$ with all the same elements but without $x$. Likewise, for any subset of $N$ which does not include $x$, there is exactly one subset of $N$ with all the same elements but also including $x$.
Let's call any two subsets of $N$ that are related in this way (i.e. one can be obtained from the other by adding/removing $x$) a corresponding pair. Note that every subset of $N$ is a member of exactly one corresponding pair. Also, in any corresponding pair one of the sets is even and the other is odd. Therefore, the number of even subsets and the number of odd subsets is the same, so LHS = RHS.
answered Jan 28 at 19:37
AlexAlex
52538
$endgroup$
$begingroup$
Thank you, I am a little bit confused about the first sentence. "Let's call the $n$ element set we're dividing up $N$". What is the $N$?---Any subset of $n$? I write it down, how I understand this. Suppose that we have $n$-element set ${1,2,3,cdots}$. We are dividing up $N$, for example $N = {1, 3, 4}$. We fix element $1$. Now, we have the following subsets; first which contain $1$: ${1}, {1, 3}, {1, 4}, {1,3,4}$; second that do not contain $1$: $emptyset, {3}, {4}, {3,4}$. These subsets are differ only by element $1$. Correct me, if I am wrong.
$endgroup$
– Kapur
Jan 28 at 20:06
$begingroup$
@Kapur $N$ is just any $n$ element set. For simplicity we can say it is ${1, 2, ldots, n}$. We want to show that the number of even size subsets of $N$ is the same as the number of odd size subsets of $N$, which corresponds to RHS = LHS in your problem.
$endgroup$
– Alex
Jan 28 at 20:12
$begingroup$
Now, it seems better.
$endgroup$
– Kapur
Jan 28 at 20:21
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%2f3091273%2fcombinatorial-proof-of-n-choose-1-n-choose-3-cdots-n-choose-0%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 call a set even if it has an even number of elements and odd if it has an odd number of elements. As @KevinLong stated in the comments, the LHS counts the number of odd subsets of $n$ elements and the RHS counts the number of even subsets of $n$ elements.
Let's call the $n$ element set we're dividing up $N$. Fix some arbitrary element $x in N$. We can partition the set of subsets of $N$ by whether they include $x$. For any subset of $N$ which includes $x$, there is exactly one subset of $N$ with all the same elements but without $x$. Likewise, for any subset of $N$ which does not include $x$, there is exactly one subset of $N$ with all the same elements but also including $x$.
Let's call any two subsets of $N$ that are related in this way (i.e. one can be obtained from the other by adding/removing $x$) a corresponding pair. Note that every subset of $N$ is a member of exactly one corresponding pair. Also, in any corresponding pair one of the sets is even and the other is odd. Therefore, the number of even subsets and the number of odd subsets is the same, so LHS = RHS.
answered Jan 28 at 19:37
AlexAlex
52538
$endgroup$
$begingroup$
Thank you, I am a little bit confused about the first sentence. "Let's call the $n$ element set we're dividing up $N$". What is the $N$?---Any subset of $n$? I write it down, how I understand this. Suppose that we have $n$-element set ${1,2,3,cdots}$. We are dividing up $N$, for example $N = {1, 3, 4}$. We fix element $1$. Now, we have the following subsets; first which contain $1$: ${1}, {1, 3}, {1, 4}, {1,3,4}$; second that do not contain $1$: $emptyset, {3}, {4}, {3,4}$. These subsets are differ only by element $1$. Correct me, if I am wrong.
$endgroup$
– Kapur
Jan 28 at 20:06
$begingroup$
@Kapur $N$ is just any $n$ element set. For simplicity we can say it is ${1, 2, ldots, n}$. We want to show that the number of even size subsets of $N$ is the same as the number of odd size subsets of $N$, which corresponds to RHS = LHS in your problem.
$endgroup$
– Alex
Jan 28 at 20:12
$begingroup$
Now, it seems better.
$endgroup$
– Kapur
Jan 28 at 20:21
add a comment |
$begingroup$
Let's call a set even if it has an even number of elements and odd if it has an odd number of elements. As @KevinLong stated in the comments, the LHS counts the number of odd subsets of $n$ elements and the RHS counts the number of even subsets of $n$ elements.
Let's call the $n$ element set we're dividing up $N$. Fix some arbitrary element $x in N$. We can partition the set of subsets of $N$ by whether they include $x$. For any subset of $N$ which includes $x$, there is exactly one subset of $N$ with all the same elements but without $x$. Likewise, for any subset of $N$ which does not include $x$, there is exactly one subset of $N$ with all the same elements but also including $x$.
Let's call any two subsets of $N$ that are related in this way (i.e. one can be obtained from the other by adding/removing $x$) a corresponding pair. Note that every subset of $N$ is a member of exactly one corresponding pair. Also, in any corresponding pair one of the sets is even and the other is odd. Therefore, the number of even subsets and the number of odd subsets is the same, so LHS = RHS.
answered Jan 28 at 19:37
AlexAlex
52538
$endgroup$
$begingroup$
Thank you, I am a little bit confused about the first sentence. "Let's call the $n$ element set we're dividing up $N$". What is the $N$?---Any subset of $n$? I write it down, how I understand this. Suppose that we have $n$-element set ${1,2,3,cdots}$. We are dividing up $N$, for example $N = {1, 3, 4}$. We fix element $1$. Now, we have the following subsets; first which contain $1$: ${1}, {1, 3}, {1, 4}, {1,3,4}$; second that do not contain $1$: $emptyset, {3}, {4}, {3,4}$. These subsets are differ only by element $1$. Correct me, if I am wrong.
$endgroup$
– Kapur
Jan 28 at 20:06
$begingroup$
@Kapur $N$ is just any $n$ element set. For simplicity we can say it is ${1, 2, ldots, n}$. We want to show that the number of even size subsets of $N$ is the same as the number of odd size subsets of $N$, which corresponds to RHS = LHS in your problem.
$endgroup$
– Alex
Jan 28 at 20:12
$begingroup$
Now, it seems better.
$endgroup$
– Kapur
Jan 28 at 20:21
add a comment |
$begingroup$
Let's call a set even if it has an even number of elements and odd if it has an odd number of elements. As @KevinLong stated in the comments, the LHS counts the number of odd subsets of $n$ elements and the RHS counts the number of even subsets of $n$ elements.
Let's call the $n$ element set we're dividing up $N$. Fix some arbitrary element $x in N$. We can partition the set of subsets of $N$ by whether they include $x$. For any subset of $N$ which includes $x$, there is exactly one subset of $N$ with all the same elements but without $x$. Likewise, for any subset of $N$ which does not include $x$, there is exactly one subset of $N$ with all the same elements but also including $x$.
Let's call any two subsets of $N$ that are related in this way (i.e. one can be obtained from the other by adding/removing $x$) a corresponding pair. Note that every subset of $N$ is a member of exactly one corresponding pair. Also, in any corresponding pair one of the sets is even and the other is odd. Therefore, the number of even subsets and the number of odd subsets is the same, so LHS = RHS.
answered Jan 28 at 19:37
AlexAlex
52538
$endgroup$
Let's call a set even if it has an even number of elements and odd if it has an odd number of elements. As @KevinLong stated in the comments, the LHS counts the number of odd subsets of $n$ elements and the RHS counts the number of even subsets of $n$ elements.
Let's call the $n$ element set we're dividing up $N$. Fix some arbitrary element $x in N$. We can partition the set of subsets of $N$ by whether they include $x$. For any subset of $N$ which includes $x$, there is exactly one subset of $N$ with all the same elements but without $x$. Likewise, for any subset of $N$ which does not include $x$, there is exactly one subset of $N$ with all the same elements but also including $x$.
Let's call any two subsets of $N$ that are related in this way (i.e. one can be obtained from the other by adding/removing $x$) a corresponding pair. Note that every subset of $N$ is a member of exactly one corresponding pair. Also, in any corresponding pair one of the sets is even and the other is odd. Therefore, the number of even subsets and the number of odd subsets is the same, so LHS = RHS.
answered Jan 28 at 19:37
AlexAlex
52538
answered Jan 28 at 19:37
AlexAlex
52538
answered Jan 28 at 19:37
AlexAlex
52538
answered Jan 28 at 19:37
AlexAlex
52538
52538
$begingroup$
Thank you, I am a little bit confused about the first sentence. "Let's call the $n$ element set we're dividing up $N$". What is the $N$?---Any subset of $n$? I write it down, how I understand this. Suppose that we have $n$-element set ${1,2,3,cdots}$. We are dividing up $N$, for example $N = {1, 3, 4}$. We fix element $1$. Now, we have the following subsets; first which contain $1$: ${1}, {1, 3}, {1, 4}, {1,3,4}$; second that do not contain $1$: $emptyset, {3}, {4}, {3,4}$. These subsets are differ only by element $1$. Correct me, if I am wrong.
$endgroup$
– Kapur
Jan 28 at 20:06
$begingroup$
@Kapur $N$ is just any $n$ element set. For simplicity we can say it is ${1, 2, ldots, n}$. We want to show that the number of even size subsets of $N$ is the same as the number of odd size subsets of $N$, which corresponds to RHS = LHS in your problem.
$endgroup$
– Alex
Jan 28 at 20:12
$begingroup$
Now, it seems better.
$endgroup$
– Kapur
Jan 28 at 20:21
add a comment |
$begingroup$
Thank you, I am a little bit confused about the first sentence. "Let's call the $n$ element set we're dividing up $N$". What is the $N$?---Any subset of $n$? I write it down, how I understand this. Suppose that we have $n$-element set ${1,2,3,cdots}$. We are dividing up $N$, for example $N = {1, 3, 4}$. We fix element $1$. Now, we have the following subsets; first which contain $1$: ${1}, {1, 3}, {1, 4}, {1,3,4}$; second that do not contain $1$: $emptyset, {3}, {4}, {3,4}$. These subsets are differ only by element $1$. Correct me, if I am wrong.
$endgroup$
– Kapur
Jan 28 at 20:06
$begingroup$
@Kapur $N$ is just any $n$ element set. For simplicity we can say it is ${1, 2, ldots, n}$. We want to show that the number of even size subsets of $N$ is the same as the number of odd size subsets of $N$, which corresponds to RHS = LHS in your problem.
$endgroup$
– Alex
Jan 28 at 20:12
$begingroup$
Now, it seems better.
$endgroup$
– Kapur
Jan 28 at 20:21
$begingroup$
Thank you, I am a little bit confused about the first sentence. "Let's call the $n$ element set we're dividing up $N$". What is the $N$?---Any subset of $n$? I write it down, how I understand this. Suppose that we have $n$-element set ${1,2,3,cdots}$. We are dividing up $N$, for example $N = {1, 3, 4}$. We fix element $1$. Now, we have the following subsets; first which contain $1$: ${1}, {1, 3}, {1, 4}, {1,3,4}$; second that do not contain $1$: $emptyset, {3}, {4}, {3,4}$. These subsets are differ only by element $1$. Correct me, if I am wrong.
$endgroup$
– Kapur
Jan 28 at 20:06
$begingroup$
Thank you, I am a little bit confused about the first sentence. "Let's call the $n$ element set we're dividing up $N$". What is the $N$?---Any subset of $n$? I write it down, how I understand this. Suppose that we have $n$-element set ${1,2,3,cdots}$. We are dividing up $N$, for example $N = {1, 3, 4}$. We fix element $1$. Now, we have the following subsets; first which contain $1$: ${1}, {1, 3}, {1, 4}, {1,3,4}$; second that do not contain $1$: $emptyset, {3}, {4}, {3,4}$. These subsets are differ only by element $1$. Correct me, if I am wrong.
$endgroup$
– Kapur
Jan 28 at 20:06
$begingroup$
@Kapur $N$ is just any $n$ element set. For simplicity we can say it is ${1, 2, ldots, n}$. We want to show that the number of even size subsets of $N$ is the same as the number of odd size subsets of $N$, which corresponds to RHS = LHS in your problem.
$endgroup$
– Alex
Jan 28 at 20:12
$begingroup$
@Kapur $N$ is just any $n$ element set. For simplicity we can say it is ${1, 2, ldots, n}$. We want to show that the number of even size subsets of $N$ is the same as the number of odd size subsets of $N$, which corresponds to RHS = LHS in your problem.
$endgroup$
– Alex
Jan 28 at 20:12
$begingroup$
Now, it seems better.
$endgroup$
– Kapur
Jan 28 at 20:21
$begingroup$
Now, it seems better.
$endgroup$
– Kapur
Jan 28 at 20:21
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%2f3091273%2fcombinatorial-proof-of-n-choose-1-n-choose-3-cdots-n-choose-0%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
2
$begingroup$
Let $[n]={1,2,ldots,n}$. The left hand side counts subsets of $[n]$ with an odd number of elements, while the right hand side counts subsets of $[n]$ with an even number of elements. How could you go from one to the other and back?
$endgroup$
– Kevin Long
Jan 28 at 19:13