Mixing
How to compute this combinatoric sum? [duplicate]
$begingroup$
This question already has an answer here:
Sum of $k {n choose k}$ is $n2^{n-1}$
4 answers
$sum_{k=0}^n k binom{n}k=ncdot2^{n-1}$
2 answers
I have the sum
$$sum_{k=0}^{n} binom{n}{k} k$$
I know the result is $n 2^{n-1}$ but I don't know how you get there. How does one even begin to simplify a sum like this that has binomial coefficients.
combinatorics number-theory summation proof-explanation
asked Jan 22 at 14:26
user525966user525966
2,1101023
$endgroup$
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();
}
);
});
});
Jan 22 at 14:58
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 |
$begingroup$
This question already has an answer here:
Sum of $k {n choose k}$ is $n2^{n-1}$
4 answers
$sum_{k=0}^n k binom{n}k=ncdot2^{n-1}$
2 answers
I have the sum
$$sum_{k=0}^{n} binom{n}{k} k$$
I know the result is $n 2^{n-1}$ but I don't know how you get there. How does one even begin to simplify a sum like this that has binomial coefficients.
combinatorics number-theory summation proof-explanation
asked Jan 22 at 14:26
user525966user525966
2,1101023
$endgroup$
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();
}
);
});
});
Jan 22 at 14:58
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.
$begingroup$
math.stackexchange.com/questions/231596/…
$endgroup$
– caverac
Jan 22 at 14:31
$begingroup$
This sum is known as $$sum_{k=0}^nbinom{n}{k}cdot k=ncdot 2^{n-1}$$
$endgroup$
– Dr. Sonnhard Graubner
Jan 22 at 14:32
add a comment |
$begingroup$
This question already has an answer here:
Sum of $k {n choose k}$ is $n2^{n-1}$
4 answers
$sum_{k=0}^n k binom{n}k=ncdot2^{n-1}$
2 answers
I have the sum
$$sum_{k=0}^{n} binom{n}{k} k$$
I know the result is $n 2^{n-1}$ but I don't know how you get there. How does one even begin to simplify a sum like this that has binomial coefficients.
combinatorics number-theory summation proof-explanation
asked Jan 22 at 14:26
user525966user525966
2,1101023
$endgroup$
This question already has an answer here:
Sum of $k {n choose k}$ is $n2^{n-1}$
4 answers
$sum_{k=0}^n k binom{n}k=ncdot2^{n-1}$
2 answers
I have the sum
$$sum_{k=0}^{n} binom{n}{k} k$$
I know the result is $n 2^{n-1}$ but I don't know how you get there. How does one even begin to simplify a sum like this that has binomial coefficients.
This question already has an answer here:
Sum of $k {n choose k}$ is $n2^{n-1}$
4 answers
$sum_{k=0}^n k binom{n}k=ncdot2^{n-1}$
2 answers
combinatorics number-theory summation proof-explanation
combinatorics number-theory summation proof-explanation
asked Jan 22 at 14:26
user525966user525966
2,1101023
asked Jan 22 at 14:26
user525966user525966
2,1101023
asked Jan 22 at 14:26
user525966user525966
2,1101023
asked Jan 22 at 14:26
user525966user525966
2,1101023
asked Jan 22 at 14:26
user525966user525966
2,1101023
2,1101023
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();
}
);
});
});
Jan 22 at 14:58
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();
}
);
});
});
Jan 22 at 14:58
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.
$begingroup$
math.stackexchange.com/questions/231596/…
$endgroup$
– caverac
Jan 22 at 14:31
$begingroup$
This sum is known as $$sum_{k=0}^nbinom{n}{k}cdot k=ncdot 2^{n-1}$$
$endgroup$
– Dr. Sonnhard Graubner
Jan 22 at 14:32
add a comment |
$begingroup$
math.stackexchange.com/questions/231596/…
$endgroup$
– caverac
Jan 22 at 14:31
$begingroup$
This sum is known as $$sum_{k=0}^nbinom{n}{k}cdot k=ncdot 2^{n-1}$$
$endgroup$
– Dr. Sonnhard Graubner
Jan 22 at 14:32
$begingroup$
math.stackexchange.com/questions/231596/…
$endgroup$
– caverac
Jan 22 at 14:31
$begingroup$
math.stackexchange.com/questions/231596/…
$endgroup$
– caverac
Jan 22 at 14:31
$begingroup$
This sum is known as $$sum_{k=0}^nbinom{n}{k}cdot k=ncdot 2^{n-1}$$
$endgroup$
– Dr. Sonnhard Graubner
Jan 22 at 14:32
$begingroup$
This sum is known as $$sum_{k=0}^nbinom{n}{k}cdot k=ncdot 2^{n-1}$$
$endgroup$
– Dr. Sonnhard Graubner
Jan 22 at 14:32
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
We have
$$sum_{k=0}^{n} kbinom{n}{k}= sum_{k=1}^{n-1} kbinom{n}{k}+n=sum_{k=1}^{n-1} nbinom{n-1}{k-1}+n=nsum_{k=0}^{n-1} binom{n-1}{k}=n2^{n-1},$$
where the last equality follows from the binomial theorem :$$2^l=(1+1)^l=sum_{k=0}^{l} binom{l}{k}1^k1^{l-k}=sum_{k=0}^{l} binom{l}{k}.$$
answered Jan 22 at 14:47
triitrii
2385
$endgroup$
add a comment |
$begingroup$
Hint:
Just differentiate $(1+x)^n = sum_{k=0}^nbinom{n}{k}x^k$ and set $x= 1$
answered Jan 22 at 14:33
trancelocationtrancelocation
12.6k1826
$endgroup$
$begingroup$
Doesn't this require knowing the answer in advance? How would we even know to try differentiating this?
$endgroup$
– user525966
Jan 22 at 15:11
add a comment |
$begingroup$
Hint:
Use the equality $$binom{n}{k}k=nbinom{n-1}{k-1}$$
answered Jan 22 at 14:46
drhabdrhab
103k545136
$endgroup$
$begingroup$
How would I know to use this trick / why does it even work?
$endgroup$
– user525966
Jan 22 at 15:11
$begingroup$
For that see the answer of @trii
$endgroup$
– drhab
Jan 22 at 16:34
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We have
$$sum_{k=0}^{n} kbinom{n}{k}= sum_{k=1}^{n-1} kbinom{n}{k}+n=sum_{k=1}^{n-1} nbinom{n-1}{k-1}+n=nsum_{k=0}^{n-1} binom{n-1}{k}=n2^{n-1},$$
where the last equality follows from the binomial theorem :$$2^l=(1+1)^l=sum_{k=0}^{l} binom{l}{k}1^k1^{l-k}=sum_{k=0}^{l} binom{l}{k}.$$
answered Jan 22 at 14:47
triitrii
2385
$endgroup$
add a comment |
$begingroup$
We have
$$sum_{k=0}^{n} kbinom{n}{k}= sum_{k=1}^{n-1} kbinom{n}{k}+n=sum_{k=1}^{n-1} nbinom{n-1}{k-1}+n=nsum_{k=0}^{n-1} binom{n-1}{k}=n2^{n-1},$$
where the last equality follows from the binomial theorem :$$2^l=(1+1)^l=sum_{k=0}^{l} binom{l}{k}1^k1^{l-k}=sum_{k=0}^{l} binom{l}{k}.$$
answered Jan 22 at 14:47
triitrii
2385
$endgroup$
add a comment |
$begingroup$
We have
$$sum_{k=0}^{n} kbinom{n}{k}= sum_{k=1}^{n-1} kbinom{n}{k}+n=sum_{k=1}^{n-1} nbinom{n-1}{k-1}+n=nsum_{k=0}^{n-1} binom{n-1}{k}=n2^{n-1},$$
where the last equality follows from the binomial theorem :$$2^l=(1+1)^l=sum_{k=0}^{l} binom{l}{k}1^k1^{l-k}=sum_{k=0}^{l} binom{l}{k}.$$
answered Jan 22 at 14:47
triitrii
2385
$endgroup$
We have
$$sum_{k=0}^{n} kbinom{n}{k}= sum_{k=1}^{n-1} kbinom{n}{k}+n=sum_{k=1}^{n-1} nbinom{n-1}{k-1}+n=nsum_{k=0}^{n-1} binom{n-1}{k}=n2^{n-1},$$
where the last equality follows from the binomial theorem :$$2^l=(1+1)^l=sum_{k=0}^{l} binom{l}{k}1^k1^{l-k}=sum_{k=0}^{l} binom{l}{k}.$$
answered Jan 22 at 14:47
triitrii
2385
edited Jan 22 at 14:52
answered Jan 22 at 14:47
triitrii
2385
answered Jan 22 at 14:47
triitrii
2385
answered Jan 22 at 14:47
triitrii
2385
2385
add a comment |
add a comment |
$begingroup$
Hint:
Just differentiate $(1+x)^n = sum_{k=0}^nbinom{n}{k}x^k$ and set $x= 1$
answered Jan 22 at 14:33
trancelocationtrancelocation
12.6k1826
$endgroup$
$begingroup$
Doesn't this require knowing the answer in advance? How would we even know to try differentiating this?
$endgroup$
– user525966
Jan 22 at 15:11
add a comment |
$begingroup$
Hint:
Just differentiate $(1+x)^n = sum_{k=0}^nbinom{n}{k}x^k$ and set $x= 1$
answered Jan 22 at 14:33
trancelocationtrancelocation
12.6k1826
$endgroup$
$begingroup$
Doesn't this require knowing the answer in advance? How would we even know to try differentiating this?
$endgroup$
– user525966
Jan 22 at 15:11
add a comment |
$begingroup$
Hint:
Just differentiate $(1+x)^n = sum_{k=0}^nbinom{n}{k}x^k$ and set $x= 1$
answered Jan 22 at 14:33
trancelocationtrancelocation
12.6k1826
$endgroup$
Hint:
Just differentiate $(1+x)^n = sum_{k=0}^nbinom{n}{k}x^k$ and set $x= 1$
answered Jan 22 at 14:33
trancelocationtrancelocation
12.6k1826
answered Jan 22 at 14:33
trancelocationtrancelocation
12.6k1826
answered Jan 22 at 14:33
trancelocationtrancelocation
12.6k1826
answered Jan 22 at 14:33
trancelocationtrancelocation
12.6k1826
12.6k1826
$begingroup$
Doesn't this require knowing the answer in advance? How would we even know to try differentiating this?
$endgroup$
– user525966
Jan 22 at 15:11
add a comment |
$begingroup$
Doesn't this require knowing the answer in advance? How would we even know to try differentiating this?
$endgroup$
– user525966
Jan 22 at 15:11
$begingroup$
Doesn't this require knowing the answer in advance? How would we even know to try differentiating this?
$endgroup$
– user525966
Jan 22 at 15:11
$begingroup$
Doesn't this require knowing the answer in advance? How would we even know to try differentiating this?
$endgroup$
– user525966
Jan 22 at 15:11
add a comment |
$begingroup$
Hint:
Use the equality $$binom{n}{k}k=nbinom{n-1}{k-1}$$
answered Jan 22 at 14:46
drhabdrhab
103k545136
$endgroup$
$begingroup$
How would I know to use this trick / why does it even work?
$endgroup$
– user525966
Jan 22 at 15:11
$begingroup$
For that see the answer of @trii
$endgroup$
– drhab
Jan 22 at 16:34
add a comment |
$begingroup$
Hint:
Use the equality $$binom{n}{k}k=nbinom{n-1}{k-1}$$
answered Jan 22 at 14:46
drhabdrhab
103k545136
$endgroup$
$begingroup$
How would I know to use this trick / why does it even work?
$endgroup$
– user525966
Jan 22 at 15:11
$begingroup$
For that see the answer of @trii
$endgroup$
– drhab
Jan 22 at 16:34
add a comment |
$begingroup$
Hint:
Use the equality $$binom{n}{k}k=nbinom{n-1}{k-1}$$
answered Jan 22 at 14:46
drhabdrhab
103k545136
$endgroup$
Hint:
Use the equality $$binom{n}{k}k=nbinom{n-1}{k-1}$$
answered Jan 22 at 14:46
drhabdrhab
103k545136
answered Jan 22 at 14:46
drhabdrhab
103k545136
answered Jan 22 at 14:46
drhabdrhab
103k545136
answered Jan 22 at 14:46
drhabdrhab
103k545136
103k545136
$begingroup$
How would I know to use this trick / why does it even work?
$endgroup$
– user525966
Jan 22 at 15:11
$begingroup$
For that see the answer of @trii
$endgroup$
– drhab
Jan 22 at 16:34
add a comment |
$begingroup$
How would I know to use this trick / why does it even work?
$endgroup$
– user525966
Jan 22 at 15:11
$begingroup$
For that see the answer of @trii
$endgroup$
– drhab
Jan 22 at 16:34
$begingroup$
How would I know to use this trick / why does it even work?
$endgroup$
– user525966
Jan 22 at 15:11
$begingroup$
How would I know to use this trick / why does it even work?
$endgroup$
– user525966
Jan 22 at 15:11
$begingroup$
For that see the answer of @trii
$endgroup$
– drhab
Jan 22 at 16:34
$begingroup$
For that see the answer of @trii
$endgroup$
– drhab
Jan 22 at 16:34
add a comment |
$begingroup$
math.stackexchange.com/questions/231596/…
$endgroup$
– caverac
Jan 22 at 14:31
$begingroup$
This sum is known as $$sum_{k=0}^nbinom{n}{k}cdot k=ncdot 2^{n-1}$$
$endgroup$
– Dr. Sonnhard Graubner
Jan 22 at 14:32