Proving $sum_{k=1}^{n} k binom{n}{k} = n cdot 2^{n-1}$ by double counting [duplicate]
up vote
3
down vote
favorite
This question already has an answer here:
Combinatorial proofs: having a difficult time understanding how to write them out
6 answers
I was given this formular, and am now tasked to use double counting to prove it:
$sum_{k=1}^{n} k binom{n}{k} = n cdot 2^{n-1}$
Quite frankly, I have no clue on how to work this out. Of course, you could start out by looking at the numbers this produces:
n result
1 1
2 4
3 12
4 32
5 80
6 192
7 448
8 1024
9 2304
10 5120
As far as I've understood double counting, there's two ways you can use it.
The first way is to imagine a matrix where you either put a tick into a field, or you leave it empty. Then counting the ticks in the rows and the columns individually must lead to the same result. Unfortunately, I see no way to apply this concept to this particular task.
The second way is to look for an intuitional problem that can be solved by either of the two ways shown in the equation. Again, I fail to come up with anything that makes sense; especially with the fact, that the sum in the left term makes everything even more complicated.
Do you have any ideas on how to solve this problem?
combinatorics
asked Nov 24 at 16:52
StckXchnge-nub12
253
marked as duplicate by N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Nov 24 at 17:17
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
up vote
3
down vote
favorite
This question already has an answer here:
Combinatorial proofs: having a difficult time understanding how to write them out
6 answers
I was given this formular, and am now tasked to use double counting to prove it:
$sum_{k=1}^{n} k binom{n}{k} = n cdot 2^{n-1}$
Quite frankly, I have no clue on how to work this out. Of course, you could start out by looking at the numbers this produces:
n result
1 1
2 4
3 12
4 32
5 80
6 192
7 448
8 1024
9 2304
10 5120
As far as I've understood double counting, there's two ways you can use it.
The first way is to imagine a matrix where you either put a tick into a field, or you leave it empty. Then counting the ticks in the rows and the columns individually must lead to the same result. Unfortunately, I see no way to apply this concept to this particular task.
The second way is to look for an intuitional problem that can be solved by either of the two ways shown in the equation. Again, I fail to come up with anything that makes sense; especially with the fact, that the sum in the left term makes everything even more complicated.
Do you have any ideas on how to solve this problem?
combinatorics
asked Nov 24 at 16:52
StckXchnge-nub12
253
marked as duplicate by N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Nov 24 at 17:17
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
math.stackexchange.com/q/2336883
– Jean-Claude Arbaut
Nov 24 at 16:59
It's likely rooted in that: $$kbinom{n}{k}+(n-k)binom{n}{n-k}=nbinom{n}{k}$$
– Rhys Hughes
Nov 24 at 17:17
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
This question already has an answer here:
Combinatorial proofs: having a difficult time understanding how to write them out
6 answers
I was given this formular, and am now tasked to use double counting to prove it:
$sum_{k=1}^{n} k binom{n}{k} = n cdot 2^{n-1}$
Quite frankly, I have no clue on how to work this out. Of course, you could start out by looking at the numbers this produces:
n result
1 1
2 4
3 12
4 32
5 80
6 192
7 448
8 1024
9 2304
10 5120
As far as I've understood double counting, there's two ways you can use it.
The first way is to imagine a matrix where you either put a tick into a field, or you leave it empty. Then counting the ticks in the rows and the columns individually must lead to the same result. Unfortunately, I see no way to apply this concept to this particular task.
The second way is to look for an intuitional problem that can be solved by either of the two ways shown in the equation. Again, I fail to come up with anything that makes sense; especially with the fact, that the sum in the left term makes everything even more complicated.
Do you have any ideas on how to solve this problem?
combinatorics
asked Nov 24 at 16:52
StckXchnge-nub12
253
This question already has an answer here:
Combinatorial proofs: having a difficult time understanding how to write them out
6 answers
I was given this formular, and am now tasked to use double counting to prove it:
$sum_{k=1}^{n} k binom{n}{k} = n cdot 2^{n-1}$
Quite frankly, I have no clue on how to work this out. Of course, you could start out by looking at the numbers this produces:
n result
1 1
2 4
3 12
4 32
5 80
6 192
7 448
8 1024
9 2304
10 5120
As far as I've understood double counting, there's two ways you can use it.
The first way is to imagine a matrix where you either put a tick into a field, or you leave it empty. Then counting the ticks in the rows and the columns individually must lead to the same result. Unfortunately, I see no way to apply this concept to this particular task.
The second way is to look for an intuitional problem that can be solved by either of the two ways shown in the equation. Again, I fail to come up with anything that makes sense; especially with the fact, that the sum in the left term makes everything even more complicated.
Do you have any ideas on how to solve this problem?
This question already has an answer here:
Combinatorial proofs: having a difficult time understanding how to write them out
6 answers
combinatorics
combinatorics
asked Nov 24 at 16:52
StckXchnge-nub12
253
asked Nov 24 at 16:52
StckXchnge-nub12
253
asked Nov 24 at 16:52
StckXchnge-nub12
253
asked Nov 24 at 16:52
StckXchnge-nub12
253
asked Nov 24 at 16:52
StckXchnge-nub12
253
253
marked as duplicate by N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Nov 24 at 17:17
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by N. F. Taussig combinatorics
Users with the combinatorics badge can single-handedly close combinatorics questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Nov 24 at 17:17
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
math.stackexchange.com/q/2336883
– Jean-Claude Arbaut
Nov 24 at 16:59
It's likely rooted in that: $$kbinom{n}{k}+(n-k)binom{n}{n-k}=nbinom{n}{k}$$
– Rhys Hughes
Nov 24 at 17:17
add a comment |
math.stackexchange.com/q/2336883
– Jean-Claude Arbaut
Nov 24 at 16:59
It's likely rooted in that: $$kbinom{n}{k}+(n-k)binom{n}{n-k}=nbinom{n}{k}$$
– Rhys Hughes
Nov 24 at 17:17
math.stackexchange.com/q/2336883
– Jean-Claude Arbaut
Nov 24 at 16:59
math.stackexchange.com/q/2336883
– Jean-Claude Arbaut
Nov 24 at 16:59
It's likely rooted in that: $$kbinom{n}{k}+(n-k)binom{n}{n-k}=nbinom{n}{k}$$
– Rhys Hughes
Nov 24 at 17:17
It's likely rooted in that: $$kbinom{n}{k}+(n-k)binom{n}{n-k}=nbinom{n}{k}$$
– Rhys Hughes
Nov 24 at 17:17
add a comment |
2 Answers
2
active
oldest
votes
up vote
4
down vote
accepted
One nice way of counting that is to think of it like this, suppose you want to choose a subset of a population of size $n$, and from this set select a leader. There are basically 2 ways of doing so, you can first choose the set of people and then choose a leader among it, if your subset is of size $k$, there are $k$ ways of choosing the leader and there are ${nchoose k}$ ways of choosing a subset of size $k$. Hence you get $sum_{k=0}^n k {nchoose k}$.
The other-way of choosing that is to select a leader from the population ($n$ ways of doing it) and then choosing the rest of the subset among the rest of the population (there $n-1$ remaining people to choose from), which accounts for $2^{n-1}$ possibilities when you fix the leader.
In conclusion
$$sum_{k=0}^n k {nchoose k}=n 2^{n-1}$$
answered Nov 24 at 17:00
P. Quinton
1,411213
I can see that it doesn't matter whether you begin the sum with $k=0$ or $k=1$ (the latter being the case in my question) since with $k=0$ that part of the sum will be $0$ anyway. Still, why do you even use a sum here? Do I understand you correctly: We want to choose only one single subset, and from this subset we want only one leader? If so, the number of possibilities for Population $n$ and subset-size $k$ should be: $binom{n}{k} cdot binom{k}{1}$. Why are we summing up things here? I'll assume the second part of your explanation will make more sense after I understand this.
– StckXchnge-nub12
Nov 24 at 17:17
Well you want to count the amount of ways you can do that, and of course the subset can have any size going from $0$ to $n$ (but for 0 there is no leader) so you need to sum for all $k$
– P. Quinton
Nov 24 at 17:21
I see. And the $2^{n-1}$ leftover possibilities after having chosen the leader first are because, for every next person you look at, there's exactly two possibilities: either they are in our subset, or they aren't in our subset. Thank you!
– StckXchnge-nub12
Nov 24 at 17:27
add a comment |
up vote
1
down vote
$sum_{k=0}^{n}kbinom{n}{k}=sum_{k=0}^{n}left(n-kright)binom{n}{k}$
so that $$sum_{k=0}^{n}kbinom{n}{k}=frac{1}{2}left[sum_{k=0}^{n}kbinom{n}{k}+sum_{k=0}^{n}left(n-kright)binom{n}{k}right]=frac{1}{2}nsum_{k=0}^{n}binom{n}{k}=frac{1}{2}n2^{n}=n2^{n-1}$$
answered Nov 24 at 17:03
drhab
95.4k543126
This looks more like a direct proof than a proof by double counting. Still, I'm interested: why is $sum_{k=0}^{infty} binom{n}{k} = 2^n$, and would this also hold for $n$ instead of $infty$ as the upper bound?
– StckXchnge-nub12
Nov 24 at 18:00
Actually it does not hold for $infty$ but for $n$. Sorry, sloppy writing. I repaired. It appears if you work out $(1+1)^n $ with binomial coefficients.
– drhab
Nov 24 at 18:15
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
One nice way of counting that is to think of it like this, suppose you want to choose a subset of a population of size $n$, and from this set select a leader. There are basically 2 ways of doing so, you can first choose the set of people and then choose a leader among it, if your subset is of size $k$, there are $k$ ways of choosing the leader and there are ${nchoose k}$ ways of choosing a subset of size $k$. Hence you get $sum_{k=0}^n k {nchoose k}$.
The other-way of choosing that is to select a leader from the population ($n$ ways of doing it) and then choosing the rest of the subset among the rest of the population (there $n-1$ remaining people to choose from), which accounts for $2^{n-1}$ possibilities when you fix the leader.
In conclusion
$$sum_{k=0}^n k {nchoose k}=n 2^{n-1}$$
answered Nov 24 at 17:00
P. Quinton
1,411213
I can see that it doesn't matter whether you begin the sum with $k=0$ or $k=1$ (the latter being the case in my question) since with $k=0$ that part of the sum will be $0$ anyway. Still, why do you even use a sum here? Do I understand you correctly: We want to choose only one single subset, and from this subset we want only one leader? If so, the number of possibilities for Population $n$ and subset-size $k$ should be: $binom{n}{k} cdot binom{k}{1}$. Why are we summing up things here? I'll assume the second part of your explanation will make more sense after I understand this.
– StckXchnge-nub12
Nov 24 at 17:17
Well you want to count the amount of ways you can do that, and of course the subset can have any size going from $0$ to $n$ (but for 0 there is no leader) so you need to sum for all $k$
– P. Quinton
Nov 24 at 17:21
I see. And the $2^{n-1}$ leftover possibilities after having chosen the leader first are because, for every next person you look at, there's exactly two possibilities: either they are in our subset, or they aren't in our subset. Thank you!
– StckXchnge-nub12
Nov 24 at 17:27
add a comment |
up vote
4
down vote
accepted
One nice way of counting that is to think of it like this, suppose you want to choose a subset of a population of size $n$, and from this set select a leader. There are basically 2 ways of doing so, you can first choose the set of people and then choose a leader among it, if your subset is of size $k$, there are $k$ ways of choosing the leader and there are ${nchoose k}$ ways of choosing a subset of size $k$. Hence you get $sum_{k=0}^n k {nchoose k}$.
The other-way of choosing that is to select a leader from the population ($n$ ways of doing it) and then choosing the rest of the subset among the rest of the population (there $n-1$ remaining people to choose from), which accounts for $2^{n-1}$ possibilities when you fix the leader.
In conclusion
$$sum_{k=0}^n k {nchoose k}=n 2^{n-1}$$
answered Nov 24 at 17:00
P. Quinton
1,411213
I can see that it doesn't matter whether you begin the sum with $k=0$ or $k=1$ (the latter being the case in my question) since with $k=0$ that part of the sum will be $0$ anyway. Still, why do you even use a sum here? Do I understand you correctly: We want to choose only one single subset, and from this subset we want only one leader? If so, the number of possibilities for Population $n$ and subset-size $k$ should be: $binom{n}{k} cdot binom{k}{1}$. Why are we summing up things here? I'll assume the second part of your explanation will make more sense after I understand this.
– StckXchnge-nub12
Nov 24 at 17:17
Well you want to count the amount of ways you can do that, and of course the subset can have any size going from $0$ to $n$ (but for 0 there is no leader) so you need to sum for all $k$
– P. Quinton
Nov 24 at 17:21
I see. And the $2^{n-1}$ leftover possibilities after having chosen the leader first are because, for every next person you look at, there's exactly two possibilities: either they are in our subset, or they aren't in our subset. Thank you!
– StckXchnge-nub12
Nov 24 at 17:27
add a comment |
up vote
4
down vote
accepted
up vote
4
down vote
accepted
One nice way of counting that is to think of it like this, suppose you want to choose a subset of a population of size $n$, and from this set select a leader. There are basically 2 ways of doing so, you can first choose the set of people and then choose a leader among it, if your subset is of size $k$, there are $k$ ways of choosing the leader and there are ${nchoose k}$ ways of choosing a subset of size $k$. Hence you get $sum_{k=0}^n k {nchoose k}$.
The other-way of choosing that is to select a leader from the population ($n$ ways of doing it) and then choosing the rest of the subset among the rest of the population (there $n-1$ remaining people to choose from), which accounts for $2^{n-1}$ possibilities when you fix the leader.
In conclusion
$$sum_{k=0}^n k {nchoose k}=n 2^{n-1}$$
answered Nov 24 at 17:00
P. Quinton
1,411213
One nice way of counting that is to think of it like this, suppose you want to choose a subset of a population of size $n$, and from this set select a leader. There are basically 2 ways of doing so, you can first choose the set of people and then choose a leader among it, if your subset is of size $k$, there are $k$ ways of choosing the leader and there are ${nchoose k}$ ways of choosing a subset of size $k$. Hence you get $sum_{k=0}^n k {nchoose k}$.
The other-way of choosing that is to select a leader from the population ($n$ ways of doing it) and then choosing the rest of the subset among the rest of the population (there $n-1$ remaining people to choose from), which accounts for $2^{n-1}$ possibilities when you fix the leader.
In conclusion
$$sum_{k=0}^n k {nchoose k}=n 2^{n-1}$$
answered Nov 24 at 17:00
P. Quinton
1,411213
answered Nov 24 at 17:00
P. Quinton
1,411213
answered Nov 24 at 17:00
P. Quinton
1,411213
answered Nov 24 at 17:00
P. Quinton
1,411213
1,411213
I can see that it doesn't matter whether you begin the sum with $k=0$ or $k=1$ (the latter being the case in my question) since with $k=0$ that part of the sum will be $0$ anyway. Still, why do you even use a sum here? Do I understand you correctly: We want to choose only one single subset, and from this subset we want only one leader? If so, the number of possibilities for Population $n$ and subset-size $k$ should be: $binom{n}{k} cdot binom{k}{1}$. Why are we summing up things here? I'll assume the second part of your explanation will make more sense after I understand this.
– StckXchnge-nub12
Nov 24 at 17:17
Well you want to count the amount of ways you can do that, and of course the subset can have any size going from $0$ to $n$ (but for 0 there is no leader) so you need to sum for all $k$
– P. Quinton
Nov 24 at 17:21
I see. And the $2^{n-1}$ leftover possibilities after having chosen the leader first are because, for every next person you look at, there's exactly two possibilities: either they are in our subset, or they aren't in our subset. Thank you!
– StckXchnge-nub12
Nov 24 at 17:27
add a comment |
I can see that it doesn't matter whether you begin the sum with $k=0$ or $k=1$ (the latter being the case in my question) since with $k=0$ that part of the sum will be $0$ anyway. Still, why do you even use a sum here? Do I understand you correctly: We want to choose only one single subset, and from this subset we want only one leader? If so, the number of possibilities for Population $n$ and subset-size $k$ should be: $binom{n}{k} cdot binom{k}{1}$. Why are we summing up things here? I'll assume the second part of your explanation will make more sense after I understand this.
– StckXchnge-nub12
Nov 24 at 17:17
Well you want to count the amount of ways you can do that, and of course the subset can have any size going from $0$ to $n$ (but for 0 there is no leader) so you need to sum for all $k$
– P. Quinton
Nov 24 at 17:21
I see. And the $2^{n-1}$ leftover possibilities after having chosen the leader first are because, for every next person you look at, there's exactly two possibilities: either they are in our subset, or they aren't in our subset. Thank you!
– StckXchnge-nub12
Nov 24 at 17:27
I can see that it doesn't matter whether you begin the sum with $k=0$ or $k=1$ (the latter being the case in my question) since with $k=0$ that part of the sum will be $0$ anyway. Still, why do you even use a sum here? Do I understand you correctly: We want to choose only one single subset, and from this subset we want only one leader? If so, the number of possibilities for Population $n$ and subset-size $k$ should be: $binom{n}{k} cdot binom{k}{1}$. Why are we summing up things here? I'll assume the second part of your explanation will make more sense after I understand this.
– StckXchnge-nub12
Nov 24 at 17:17
I can see that it doesn't matter whether you begin the sum with $k=0$ or $k=1$ (the latter being the case in my question) since with $k=0$ that part of the sum will be $0$ anyway. Still, why do you even use a sum here? Do I understand you correctly: We want to choose only one single subset, and from this subset we want only one leader? If so, the number of possibilities for Population $n$ and subset-size $k$ should be: $binom{n}{k} cdot binom{k}{1}$. Why are we summing up things here? I'll assume the second part of your explanation will make more sense after I understand this.
– StckXchnge-nub12
Nov 24 at 17:17
Well you want to count the amount of ways you can do that, and of course the subset can have any size going from $0$ to $n$ (but for 0 there is no leader) so you need to sum for all $k$
– P. Quinton
Nov 24 at 17:21
Well you want to count the amount of ways you can do that, and of course the subset can have any size going from $0$ to $n$ (but for 0 there is no leader) so you need to sum for all $k$
– P. Quinton
Nov 24 at 17:21
I see. And the $2^{n-1}$ leftover possibilities after having chosen the leader first are because, for every next person you look at, there's exactly two possibilities: either they are in our subset, or they aren't in our subset. Thank you!
– StckXchnge-nub12
Nov 24 at 17:27
I see. And the $2^{n-1}$ leftover possibilities after having chosen the leader first are because, for every next person you look at, there's exactly two possibilities: either they are in our subset, or they aren't in our subset. Thank you!
– StckXchnge-nub12
Nov 24 at 17:27
add a comment |
up vote
1
down vote
$sum_{k=0}^{n}kbinom{n}{k}=sum_{k=0}^{n}left(n-kright)binom{n}{k}$
so that $$sum_{k=0}^{n}kbinom{n}{k}=frac{1}{2}left[sum_{k=0}^{n}kbinom{n}{k}+sum_{k=0}^{n}left(n-kright)binom{n}{k}right]=frac{1}{2}nsum_{k=0}^{n}binom{n}{k}=frac{1}{2}n2^{n}=n2^{n-1}$$
answered Nov 24 at 17:03
drhab
95.4k543126
This looks more like a direct proof than a proof by double counting. Still, I'm interested: why is $sum_{k=0}^{infty} binom{n}{k} = 2^n$, and would this also hold for $n$ instead of $infty$ as the upper bound?
– StckXchnge-nub12
Nov 24 at 18:00
Actually it does not hold for $infty$ but for $n$. Sorry, sloppy writing. I repaired. It appears if you work out $(1+1)^n $ with binomial coefficients.
– drhab
Nov 24 at 18:15
add a comment |
up vote
1
down vote
$sum_{k=0}^{n}kbinom{n}{k}=sum_{k=0}^{n}left(n-kright)binom{n}{k}$
so that $$sum_{k=0}^{n}kbinom{n}{k}=frac{1}{2}left[sum_{k=0}^{n}kbinom{n}{k}+sum_{k=0}^{n}left(n-kright)binom{n}{k}right]=frac{1}{2}nsum_{k=0}^{n}binom{n}{k}=frac{1}{2}n2^{n}=n2^{n-1}$$
answered Nov 24 at 17:03
drhab
95.4k543126
This looks more like a direct proof than a proof by double counting. Still, I'm interested: why is $sum_{k=0}^{infty} binom{n}{k} = 2^n$, and would this also hold for $n$ instead of $infty$ as the upper bound?
– StckXchnge-nub12
Nov 24 at 18:00
Actually it does not hold for $infty$ but for $n$. Sorry, sloppy writing. I repaired. It appears if you work out $(1+1)^n $ with binomial coefficients.
– drhab
Nov 24 at 18:15
add a comment |
up vote
1
down vote
up vote
1
down vote
$sum_{k=0}^{n}kbinom{n}{k}=sum_{k=0}^{n}left(n-kright)binom{n}{k}$
so that $$sum_{k=0}^{n}kbinom{n}{k}=frac{1}{2}left[sum_{k=0}^{n}kbinom{n}{k}+sum_{k=0}^{n}left(n-kright)binom{n}{k}right]=frac{1}{2}nsum_{k=0}^{n}binom{n}{k}=frac{1}{2}n2^{n}=n2^{n-1}$$
answered Nov 24 at 17:03
drhab
95.4k543126
$sum_{k=0}^{n}kbinom{n}{k}=sum_{k=0}^{n}left(n-kright)binom{n}{k}$
so that $$sum_{k=0}^{n}kbinom{n}{k}=frac{1}{2}left[sum_{k=0}^{n}kbinom{n}{k}+sum_{k=0}^{n}left(n-kright)binom{n}{k}right]=frac{1}{2}nsum_{k=0}^{n}binom{n}{k}=frac{1}{2}n2^{n}=n2^{n-1}$$
answered Nov 24 at 17:03
drhab
95.4k543126
edited Nov 24 at 18:10
answered Nov 24 at 17:03
drhab
95.4k543126
answered Nov 24 at 17:03
drhab
95.4k543126
answered Nov 24 at 17:03
drhab
95.4k543126
95.4k543126
This looks more like a direct proof than a proof by double counting. Still, I'm interested: why is $sum_{k=0}^{infty} binom{n}{k} = 2^n$, and would this also hold for $n$ instead of $infty$ as the upper bound?
– StckXchnge-nub12
Nov 24 at 18:00
Actually it does not hold for $infty$ but for $n$. Sorry, sloppy writing. I repaired. It appears if you work out $(1+1)^n $ with binomial coefficients.
– drhab
Nov 24 at 18:15
add a comment |
This looks more like a direct proof than a proof by double counting. Still, I'm interested: why is $sum_{k=0}^{infty} binom{n}{k} = 2^n$, and would this also hold for $n$ instead of $infty$ as the upper bound?
– StckXchnge-nub12
Nov 24 at 18:00
Actually it does not hold for $infty$ but for $n$. Sorry, sloppy writing. I repaired. It appears if you work out $(1+1)^n $ with binomial coefficients.
– drhab
Nov 24 at 18:15
This looks more like a direct proof than a proof by double counting. Still, I'm interested: why is $sum_{k=0}^{infty} binom{n}{k} = 2^n$, and would this also hold for $n$ instead of $infty$ as the upper bound?
– StckXchnge-nub12
Nov 24 at 18:00
This looks more like a direct proof than a proof by double counting. Still, I'm interested: why is $sum_{k=0}^{infty} binom{n}{k} = 2^n$, and would this also hold for $n$ instead of $infty$ as the upper bound?
– StckXchnge-nub12
Nov 24 at 18:00
Actually it does not hold for $infty$ but for $n$. Sorry, sloppy writing. I repaired. It appears if you work out $(1+1)^n $ with binomial coefficients.
– drhab
Nov 24 at 18:15
Actually it does not hold for $infty$ but for $n$. Sorry, sloppy writing. I repaired. It appears if you work out $(1+1)^n $ with binomial coefficients.
– drhab
Nov 24 at 18:15
add a comment |
math.stackexchange.com/q/2336883
– Jean-Claude Arbaut
Nov 24 at 16:59
It's likely rooted in that: $$kbinom{n}{k}+(n-k)binom{n}{n-k}=nbinom{n}{k}$$
– Rhys Hughes
Nov 24 at 17:17