Mixing
Evaluate $sumlimits_{k=0}^n binom{n}{k}$ combinatorially
$begingroup$
Please help me to evaluate combinatorially the following sum:
$$sum_{k=0}^n binom{n}{k}$$
Thank you.
combinatorics summation binomial-coefficients combinatorial-proofs
edited Sep 27 '15 at 20:38
Martin Sleziak
45k10123277
asked Apr 27 '12 at 17:16
DavidDavid
207213
$endgroup$
add a comment |
$begingroup$
Please help me to evaluate combinatorially the following sum:
$$sum_{k=0}^n binom{n}{k}$$
Thank you.
combinatorics summation binomial-coefficients combinatorial-proofs
edited Sep 27 '15 at 20:38
Martin Sleziak
45k10123277
asked Apr 27 '12 at 17:16
DavidDavid
207213
$endgroup$
$begingroup$
Hint. $(1+1)^n = ???$
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:19
3
$begingroup$
Alternative Hint. If you choose either $0$, or $1$, or $2$, or $3$, or $4,ldots,$ or $n$ elements out of $n$, then you are just choosing "some" objects out of $n$ possibilities. How many ways are there of doing that?
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:22
2
$begingroup$
Its the expansion of the series $(1+x)^n$, put x=1, to get the sum
$endgroup$
– Tomarinator
Apr 27 '12 at 17:25
1
$begingroup$
I'm quite sure this is a dupe...
$endgroup$
– J. M. is a poor mathematician
Apr 27 '12 at 17:37
1
$begingroup$
J.M maybe this math.stackexchange.com/questions/18690/…
$endgroup$
– Belgi
Apr 27 '12 at 17:39
add a comment |
$begingroup$
Please help me to evaluate combinatorially the following sum:
$$sum_{k=0}^n binom{n}{k}$$
Thank you.
combinatorics summation binomial-coefficients combinatorial-proofs
edited Sep 27 '15 at 20:38
Martin Sleziak
45k10123277
asked Apr 27 '12 at 17:16
DavidDavid
207213
$endgroup$
Please help me to evaluate combinatorially the following sum:
$$sum_{k=0}^n binom{n}{k}$$
Thank you.
combinatorics summation binomial-coefficients combinatorial-proofs
combinatorics summation binomial-coefficients combinatorial-proofs
edited Sep 27 '15 at 20:38
Martin Sleziak
45k10123277
asked Apr 27 '12 at 17:16
DavidDavid
207213
edited Sep 27 '15 at 20:38
Martin Sleziak
45k10123277
asked Apr 27 '12 at 17:16
DavidDavid
207213
edited Sep 27 '15 at 20:38
Martin Sleziak
45k10123277
edited Sep 27 '15 at 20:38
Martin Sleziak
45k10123277
edited Sep 27 '15 at 20:38
Martin Sleziak
45k10123277
45k10123277
asked Apr 27 '12 at 17:16
DavidDavid
207213
asked Apr 27 '12 at 17:16
DavidDavid
207213
asked Apr 27 '12 at 17:16
DavidDavid
207213
207213
$begingroup$
Hint. $(1+1)^n = ???$
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:19
3
$begingroup$
Alternative Hint. If you choose either $0$, or $1$, or $2$, or $3$, or $4,ldots,$ or $n$ elements out of $n$, then you are just choosing "some" objects out of $n$ possibilities. How many ways are there of doing that?
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:22
2
$begingroup$
Its the expansion of the series $(1+x)^n$, put x=1, to get the sum
$endgroup$
– Tomarinator
Apr 27 '12 at 17:25
1
$begingroup$
I'm quite sure this is a dupe...
$endgroup$
– J. M. is a poor mathematician
Apr 27 '12 at 17:37
1
$begingroup$
J.M maybe this math.stackexchange.com/questions/18690/…
$endgroup$
– Belgi
Apr 27 '12 at 17:39
add a comment |
$begingroup$
Hint. $(1+1)^n = ???$
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:19
3
$begingroup$
Alternative Hint. If you choose either $0$, or $1$, or $2$, or $3$, or $4,ldots,$ or $n$ elements out of $n$, then you are just choosing "some" objects out of $n$ possibilities. How many ways are there of doing that?
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:22
2
$begingroup$
Its the expansion of the series $(1+x)^n$, put x=1, to get the sum
$endgroup$
– Tomarinator
Apr 27 '12 at 17:25
1
$begingroup$
I'm quite sure this is a dupe...
$endgroup$
– J. M. is a poor mathematician
Apr 27 '12 at 17:37
1
$begingroup$
J.M maybe this math.stackexchange.com/questions/18690/…
$endgroup$
– Belgi
Apr 27 '12 at 17:39
$begingroup$
Hint. $(1+1)^n = ???$
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:19
$begingroup$
Hint. $(1+1)^n = ???$
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:19
3
3
$begingroup$
Alternative Hint. If you choose either $0$, or $1$, or $2$, or $3$, or $4,ldots,$ or $n$ elements out of $n$, then you are just choosing "some" objects out of $n$ possibilities. How many ways are there of doing that?
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:22
$begingroup$
Alternative Hint. If you choose either $0$, or $1$, or $2$, or $3$, or $4,ldots,$ or $n$ elements out of $n$, then you are just choosing "some" objects out of $n$ possibilities. How many ways are there of doing that?
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:22
2
2
$begingroup$
Its the expansion of the series $(1+x)^n$, put x=1, to get the sum
$endgroup$
– Tomarinator
Apr 27 '12 at 17:25
$begingroup$
Its the expansion of the series $(1+x)^n$, put x=1, to get the sum
$endgroup$
– Tomarinator
Apr 27 '12 at 17:25
1
1
$begingroup$
I'm quite sure this is a dupe...
$endgroup$
– J. M. is a poor mathematician
Apr 27 '12 at 17:37
$begingroup$
I'm quite sure this is a dupe...
$endgroup$
– J. M. is a poor mathematician
Apr 27 '12 at 17:37
1
1
$begingroup$
J.M maybe this math.stackexchange.com/questions/18690/…
$endgroup$
– Belgi
Apr 27 '12 at 17:39
$begingroup$
J.M maybe this math.stackexchange.com/questions/18690/…
$endgroup$
– Belgi
Apr 27 '12 at 17:39
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
We use the powerful strategy of counting the same thing in two different ways. We have a set $S$ of $n$ spices. We ask how many different subsets this set has.
Line up the spices in order on a shelf. Go gradually down the shelf, saying yes or no to each spice in turn. At each spice, we have two choices. So there is a total of $2^n$ choices, and hence $S$ has $2^n$ subsets.
For any $k$, there are by definition $binom{n}{k}$ ways to choose $k$ spices from the set $S$. So $S$ has $binom{n}{k}$ subsets with $k$ elements. Summing over all $k$ from $0$ to $n$ gives us a different way of counting all the subsets.
Both counting methods are correct, so they must give the same answer. It follows that
$$sum_{k=1}^n binom{n}{k}=2^n.$$
Remark: Bhaskara once asked the following question. There are $6$ basic flavours (sour, sweet, bitter, and so on). How many different-flavoured dishes can one make by using flavours selected from these? He gave the answer $63$, leaving out the empty set of flavours. He did not know about English cooking.
answered Apr 27 '12 at 17:34
André NicolasAndré Nicolas
455k36432822
$endgroup$
$begingroup$
Wow, a math post spiced with a combinatorially motivated cooking joke. And a taste of history to boot. Thanks for the chuckle.
$endgroup$
– Bill Dubuque
Apr 27 '12 at 18:55
2
$begingroup$
English cooking! /rimshot/ However, I believe you mean 6 basic flavours, not 8.
$endgroup$
– Cameron Buie
Apr 27 '12 at 19:15
$begingroup$
@CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent.
$endgroup$
– André Nicolas
Apr 27 '12 at 19:27
add a comment |
$begingroup$
I will provide an intuition why $$sum_{k=1}^n binom{n}{k}=2^n.$$
firstly, suppose you have $n$ persons, each one has two options either succeed or fail,
so you have $ 2^n $ different combinationssecondly, let's do it in another way :
we will count all the possible combination according to this rule (we choose the ones to succeed, and the rest -who fails- is determined). so we have $binom{n}{0}$ and the rest fail + $binom{n}{1}$ and the rest fails. and so on until
$binom{n}{n}$
answered Feb 2 at 21:54
Bishoy AbdBishoy Abd
1012
$endgroup$
add a comment |
Your Answer
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%2f137727%2fevaluate-sum-limits-k-0n-binomnk-combinatorially%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We use the powerful strategy of counting the same thing in two different ways. We have a set $S$ of $n$ spices. We ask how many different subsets this set has.
Line up the spices in order on a shelf. Go gradually down the shelf, saying yes or no to each spice in turn. At each spice, we have two choices. So there is a total of $2^n$ choices, and hence $S$ has $2^n$ subsets.
For any $k$, there are by definition $binom{n}{k}$ ways to choose $k$ spices from the set $S$. So $S$ has $binom{n}{k}$ subsets with $k$ elements. Summing over all $k$ from $0$ to $n$ gives us a different way of counting all the subsets.
Both counting methods are correct, so they must give the same answer. It follows that
$$sum_{k=1}^n binom{n}{k}=2^n.$$
Remark: Bhaskara once asked the following question. There are $6$ basic flavours (sour, sweet, bitter, and so on). How many different-flavoured dishes can one make by using flavours selected from these? He gave the answer $63$, leaving out the empty set of flavours. He did not know about English cooking.
answered Apr 27 '12 at 17:34
André NicolasAndré Nicolas
455k36432822
$endgroup$
$begingroup$
Wow, a math post spiced with a combinatorially motivated cooking joke. And a taste of history to boot. Thanks for the chuckle.
$endgroup$
– Bill Dubuque
Apr 27 '12 at 18:55
2
$begingroup$
English cooking! /rimshot/ However, I believe you mean 6 basic flavours, not 8.
$endgroup$
– Cameron Buie
Apr 27 '12 at 19:15
$begingroup$
@CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent.
$endgroup$
– André Nicolas
Apr 27 '12 at 19:27
add a comment |
$begingroup$
We use the powerful strategy of counting the same thing in two different ways. We have a set $S$ of $n$ spices. We ask how many different subsets this set has.
Line up the spices in order on a shelf. Go gradually down the shelf, saying yes or no to each spice in turn. At each spice, we have two choices. So there is a total of $2^n$ choices, and hence $S$ has $2^n$ subsets.
For any $k$, there are by definition $binom{n}{k}$ ways to choose $k$ spices from the set $S$. So $S$ has $binom{n}{k}$ subsets with $k$ elements. Summing over all $k$ from $0$ to $n$ gives us a different way of counting all the subsets.
Both counting methods are correct, so they must give the same answer. It follows that
$$sum_{k=1}^n binom{n}{k}=2^n.$$
Remark: Bhaskara once asked the following question. There are $6$ basic flavours (sour, sweet, bitter, and so on). How many different-flavoured dishes can one make by using flavours selected from these? He gave the answer $63$, leaving out the empty set of flavours. He did not know about English cooking.
answered Apr 27 '12 at 17:34
André NicolasAndré Nicolas
455k36432822
$endgroup$
$begingroup$
Wow, a math post spiced with a combinatorially motivated cooking joke. And a taste of history to boot. Thanks for the chuckle.
$endgroup$
– Bill Dubuque
Apr 27 '12 at 18:55
2
$begingroup$
English cooking! /rimshot/ However, I believe you mean 6 basic flavours, not 8.
$endgroup$
– Cameron Buie
Apr 27 '12 at 19:15
$begingroup$
@CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent.
$endgroup$
– André Nicolas
Apr 27 '12 at 19:27
add a comment |
$begingroup$
We use the powerful strategy of counting the same thing in two different ways. We have a set $S$ of $n$ spices. We ask how many different subsets this set has.
Line up the spices in order on a shelf. Go gradually down the shelf, saying yes or no to each spice in turn. At each spice, we have two choices. So there is a total of $2^n$ choices, and hence $S$ has $2^n$ subsets.
For any $k$, there are by definition $binom{n}{k}$ ways to choose $k$ spices from the set $S$. So $S$ has $binom{n}{k}$ subsets with $k$ elements. Summing over all $k$ from $0$ to $n$ gives us a different way of counting all the subsets.
Both counting methods are correct, so they must give the same answer. It follows that
$$sum_{k=1}^n binom{n}{k}=2^n.$$
Remark: Bhaskara once asked the following question. There are $6$ basic flavours (sour, sweet, bitter, and so on). How many different-flavoured dishes can one make by using flavours selected from these? He gave the answer $63$, leaving out the empty set of flavours. He did not know about English cooking.
answered Apr 27 '12 at 17:34
André NicolasAndré Nicolas
455k36432822
$endgroup$
We use the powerful strategy of counting the same thing in two different ways. We have a set $S$ of $n$ spices. We ask how many different subsets this set has.
Line up the spices in order on a shelf. Go gradually down the shelf, saying yes or no to each spice in turn. At each spice, we have two choices. So there is a total of $2^n$ choices, and hence $S$ has $2^n$ subsets.
For any $k$, there are by definition $binom{n}{k}$ ways to choose $k$ spices from the set $S$. So $S$ has $binom{n}{k}$ subsets with $k$ elements. Summing over all $k$ from $0$ to $n$ gives us a different way of counting all the subsets.
Both counting methods are correct, so they must give the same answer. It follows that
$$sum_{k=1}^n binom{n}{k}=2^n.$$
Remark: Bhaskara once asked the following question. There are $6$ basic flavours (sour, sweet, bitter, and so on). How many different-flavoured dishes can one make by using flavours selected from these? He gave the answer $63$, leaving out the empty set of flavours. He did not know about English cooking.
answered Apr 27 '12 at 17:34
André NicolasAndré Nicolas
455k36432822
edited Apr 27 '12 at 19:23
answered Apr 27 '12 at 17:34
André NicolasAndré Nicolas
455k36432822
answered Apr 27 '12 at 17:34
André NicolasAndré Nicolas
455k36432822
answered Apr 27 '12 at 17:34
André NicolasAndré Nicolas
455k36432822
455k36432822
$begingroup$
Wow, a math post spiced with a combinatorially motivated cooking joke. And a taste of history to boot. Thanks for the chuckle.
$endgroup$
– Bill Dubuque
Apr 27 '12 at 18:55
2
$begingroup$
English cooking! /rimshot/ However, I believe you mean 6 basic flavours, not 8.
$endgroup$
– Cameron Buie
Apr 27 '12 at 19:15
$begingroup$
@CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent.
$endgroup$
– André Nicolas
Apr 27 '12 at 19:27
add a comment |
$begingroup$
Wow, a math post spiced with a combinatorially motivated cooking joke. And a taste of history to boot. Thanks for the chuckle.
$endgroup$
– Bill Dubuque
Apr 27 '12 at 18:55
2
$begingroup$
English cooking! /rimshot/ However, I believe you mean 6 basic flavours, not 8.
$endgroup$
– Cameron Buie
Apr 27 '12 at 19:15
$begingroup$
@CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent.
$endgroup$
– André Nicolas
Apr 27 '12 at 19:27
$begingroup$
Wow, a math post spiced with a combinatorially motivated cooking joke. And a taste of history to boot. Thanks for the chuckle.
$endgroup$
– Bill Dubuque
Apr 27 '12 at 18:55
$begingroup$
Wow, a math post spiced with a combinatorially motivated cooking joke. And a taste of history to boot. Thanks for the chuckle.
$endgroup$
– Bill Dubuque
Apr 27 '12 at 18:55
2
2
$begingroup$
English cooking! /rimshot/ However, I believe you mean 6 basic flavours, not 8.
$endgroup$
– Cameron Buie
Apr 27 '12 at 19:15
$begingroup$
English cooking! /rimshot/ However, I believe you mean 6 basic flavours, not 8.
$endgroup$
– Cameron Buie
Apr 27 '12 at 19:15
$begingroup$
@CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent.
$endgroup$
– André Nicolas
Apr 27 '12 at 19:27
$begingroup$
@CameronBuie: Yes, error corrected. The other flavours are I think salty, hot, and astringent.
$endgroup$
– André Nicolas
Apr 27 '12 at 19:27
add a comment |
$begingroup$
I will provide an intuition why $$sum_{k=1}^n binom{n}{k}=2^n.$$
firstly, suppose you have $n$ persons, each one has two options either succeed or fail,
so you have $ 2^n $ different combinationssecondly, let's do it in another way :
we will count all the possible combination according to this rule (we choose the ones to succeed, and the rest -who fails- is determined). so we have $binom{n}{0}$ and the rest fail + $binom{n}{1}$ and the rest fails. and so on until
$binom{n}{n}$
answered Feb 2 at 21:54
Bishoy AbdBishoy Abd
1012
$endgroup$
add a comment |
$begingroup$
I will provide an intuition why $$sum_{k=1}^n binom{n}{k}=2^n.$$
firstly, suppose you have $n$ persons, each one has two options either succeed or fail,
so you have $ 2^n $ different combinationssecondly, let's do it in another way :
we will count all the possible combination according to this rule (we choose the ones to succeed, and the rest -who fails- is determined). so we have $binom{n}{0}$ and the rest fail + $binom{n}{1}$ and the rest fails. and so on until
$binom{n}{n}$
answered Feb 2 at 21:54
Bishoy AbdBishoy Abd
1012
$endgroup$
add a comment |
$begingroup$
I will provide an intuition why $$sum_{k=1}^n binom{n}{k}=2^n.$$
firstly, suppose you have $n$ persons, each one has two options either succeed or fail,
so you have $ 2^n $ different combinationssecondly, let's do it in another way :
we will count all the possible combination according to this rule (we choose the ones to succeed, and the rest -who fails- is determined). so we have $binom{n}{0}$ and the rest fail + $binom{n}{1}$ and the rest fails. and so on until
$binom{n}{n}$
answered Feb 2 at 21:54
Bishoy AbdBishoy Abd
1012
$endgroup$
I will provide an intuition why $$sum_{k=1}^n binom{n}{k}=2^n.$$
firstly, suppose you have $n$ persons, each one has two options either succeed or fail,
so you have $ 2^n $ different combinationssecondly, let's do it in another way :
we will count all the possible combination according to this rule (we choose the ones to succeed, and the rest -who fails- is determined). so we have $binom{n}{0}$ and the rest fail + $binom{n}{1}$ and the rest fails. and so on until
$binom{n}{n}$
answered Feb 2 at 21:54
Bishoy AbdBishoy Abd
1012
answered Feb 2 at 21:54
Bishoy AbdBishoy Abd
1012
answered Feb 2 at 21:54
Bishoy AbdBishoy Abd
1012
answered Feb 2 at 21:54
Bishoy AbdBishoy Abd
1012
1012
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%2f137727%2fevaluate-sum-limits-k-0n-binomnk-combinatorially%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
$begingroup$
Hint. $(1+1)^n = ???$
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:19
3
$begingroup$
Alternative Hint. If you choose either $0$, or $1$, or $2$, or $3$, or $4,ldots,$ or $n$ elements out of $n$, then you are just choosing "some" objects out of $n$ possibilities. How many ways are there of doing that?
$endgroup$
– Arturo Magidin
Apr 27 '12 at 17:22
2
$begingroup$
Its the expansion of the series $(1+x)^n$, put x=1, to get the sum
$endgroup$
– Tomarinator
Apr 27 '12 at 17:25
1
$begingroup$
I'm quite sure this is a dupe...
$endgroup$
– J. M. is a poor mathematician
Apr 27 '12 at 17:37
1
$begingroup$
J.M maybe this math.stackexchange.com/questions/18690/…
$endgroup$
– Belgi
Apr 27 '12 at 17:39