Prove the identity $sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} = 3^n$
$begingroup$
Prove the identity $sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} = 3^n$. I believe I need to use the binomial theorem here, but I don't know how to deal with the double summations.
combinatorics discrete-mathematics summation binomial-coefficients
$endgroup$
add a comment |
$begingroup$
Prove the identity $sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} = 3^n$. I believe I need to use the binomial theorem here, but I don't know how to deal with the double summations.
combinatorics discrete-mathematics summation binomial-coefficients
$endgroup$
$begingroup$
Use this question.
$endgroup$
– Dietrich Burde
Dec 8 '18 at 19:19
$begingroup$
You may be interested in the Multinomial theorem about multinomial coefficients.
$endgroup$
– Somos
Dec 8 '18 at 19:33
add a comment |
$begingroup$
Prove the identity $sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} = 3^n$. I believe I need to use the binomial theorem here, but I don't know how to deal with the double summations.
combinatorics discrete-mathematics summation binomial-coefficients
$endgroup$
Prove the identity $sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} = 3^n$. I believe I need to use the binomial theorem here, but I don't know how to deal with the double summations.
combinatorics discrete-mathematics summation binomial-coefficients
combinatorics discrete-mathematics summation binomial-coefficients
edited Dec 9 '18 at 15:48
Martin Sleziak
44.7k9117272
44.7k9117272
asked Dec 8 '18 at 19:13
cosmicbrowniecosmicbrownie
1016
1016
$begingroup$
Use this question.
$endgroup$
– Dietrich Burde
Dec 8 '18 at 19:19
$begingroup$
You may be interested in the Multinomial theorem about multinomial coefficients.
$endgroup$
– Somos
Dec 8 '18 at 19:33
add a comment |
$begingroup$
Use this question.
$endgroup$
– Dietrich Burde
Dec 8 '18 at 19:19
$begingroup$
You may be interested in the Multinomial theorem about multinomial coefficients.
$endgroup$
– Somos
Dec 8 '18 at 19:33
$begingroup$
Use this question.
$endgroup$
– Dietrich Burde
Dec 8 '18 at 19:19
$begingroup$
Use this question.
$endgroup$
– Dietrich Burde
Dec 8 '18 at 19:19
$begingroup$
You may be interested in the Multinomial theorem about multinomial coefficients.
$endgroup$
– Somos
Dec 8 '18 at 19:33
$begingroup$
You may be interested in the Multinomial theorem about multinomial coefficients.
$endgroup$
– Somos
Dec 8 '18 at 19:33
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
We will use the identity
$$
binom{n}{k}binom{k}{r}=binom{n}{r}binom{n-r}{k-r}quad (ngeq kgeq rgeq 0).
$$
Interchange the order of summation and use the identity above to get that
$$
sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k}
=sum_{r=0}^{n}binom{n}{r}sum_{k=r}^{n}binom{n-r}{k-r}=sum_{r=0}^nbinom{n}{r}2^{n-r}=(1+2)^n=3^n
$$
where we used the fact that
$$
sum_{k=r}^{n}binom{n-r}{k-r}=sum_{u=0}^{n-r}binom{n-r}{u}=2^{n-r}.
$$
$endgroup$
$begingroup$
Do you know a combinatorial proof of the statement?
$endgroup$
– nafhgood
Dec 8 '18 at 20:33
1
$begingroup$
@mathnoob I think I have a combinatorial argument, see my answer below.
$endgroup$
– Ned
Dec 8 '18 at 21:18
$begingroup$
That's cool! Thanks!
$endgroup$
– nafhgood
Dec 8 '18 at 21:22
add a comment |
$begingroup$
Let $|X|=n$, so $3^n$ is the number of functions from $X$ to {$1,2,3$}.
Each such function corresponds uniquely to a pair of subsets $(A,B)$ with $A$ a subset of $B$ and $B$ a subset of $X$ by taking $B$ = {$x$ | $f(x)=2$ or $f(x)=3$} and $A$ = {$x$ | $f(x)=2$}.
The number of such pairs of nested subsets of $X$ is the double sum on the right hand side of the formula (where $k$ = $|B|$ and $r$ = $|A|$).
$endgroup$
add a comment |
$begingroup$
You know that $displaystyle(1+x)^n=sum_{k=0}^nbinom nkx^k$
$displaystylesum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} =sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}=sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}1^r$
Since $displaystylesum_{r=0}^{k} binom{k}{r}1^r=(1+1)^k=2^k$, we have
$displaystyleimpliessum_{k=0}^{n} binom nk2^k=(1+2)^n=3^n$
$endgroup$
add a comment |
$begingroup$
A convenient aspect is the index of the inner sum affects only one binomial coefficient. Setting parenthesis we might observe
begin{align*}
color{blue}{sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r}binom{n}{k}}
&=sum_{k=0}^{n}left(sum_{r=0}^{k} binom{k}{r} right)binom{n}{k}\
&=sum_{k=0}^{n}2^k binom{n}{k}\
&,,color{blue}{=3^n}
end{align*}
$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%2f3031500%2fprove-the-identity-sum-k-0n-sum-r-0k-binomkr-binomnk-3n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We will use the identity
$$
binom{n}{k}binom{k}{r}=binom{n}{r}binom{n-r}{k-r}quad (ngeq kgeq rgeq 0).
$$
Interchange the order of summation and use the identity above to get that
$$
sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k}
=sum_{r=0}^{n}binom{n}{r}sum_{k=r}^{n}binom{n-r}{k-r}=sum_{r=0}^nbinom{n}{r}2^{n-r}=(1+2)^n=3^n
$$
where we used the fact that
$$
sum_{k=r}^{n}binom{n-r}{k-r}=sum_{u=0}^{n-r}binom{n-r}{u}=2^{n-r}.
$$
$endgroup$
$begingroup$
Do you know a combinatorial proof of the statement?
$endgroup$
– nafhgood
Dec 8 '18 at 20:33
1
$begingroup$
@mathnoob I think I have a combinatorial argument, see my answer below.
$endgroup$
– Ned
Dec 8 '18 at 21:18
$begingroup$
That's cool! Thanks!
$endgroup$
– nafhgood
Dec 8 '18 at 21:22
add a comment |
$begingroup$
We will use the identity
$$
binom{n}{k}binom{k}{r}=binom{n}{r}binom{n-r}{k-r}quad (ngeq kgeq rgeq 0).
$$
Interchange the order of summation and use the identity above to get that
$$
sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k}
=sum_{r=0}^{n}binom{n}{r}sum_{k=r}^{n}binom{n-r}{k-r}=sum_{r=0}^nbinom{n}{r}2^{n-r}=(1+2)^n=3^n
$$
where we used the fact that
$$
sum_{k=r}^{n}binom{n-r}{k-r}=sum_{u=0}^{n-r}binom{n-r}{u}=2^{n-r}.
$$
$endgroup$
$begingroup$
Do you know a combinatorial proof of the statement?
$endgroup$
– nafhgood
Dec 8 '18 at 20:33
1
$begingroup$
@mathnoob I think I have a combinatorial argument, see my answer below.
$endgroup$
– Ned
Dec 8 '18 at 21:18
$begingroup$
That's cool! Thanks!
$endgroup$
– nafhgood
Dec 8 '18 at 21:22
add a comment |
$begingroup$
We will use the identity
$$
binom{n}{k}binom{k}{r}=binom{n}{r}binom{n-r}{k-r}quad (ngeq kgeq rgeq 0).
$$
Interchange the order of summation and use the identity above to get that
$$
sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k}
=sum_{r=0}^{n}binom{n}{r}sum_{k=r}^{n}binom{n-r}{k-r}=sum_{r=0}^nbinom{n}{r}2^{n-r}=(1+2)^n=3^n
$$
where we used the fact that
$$
sum_{k=r}^{n}binom{n-r}{k-r}=sum_{u=0}^{n-r}binom{n-r}{u}=2^{n-r}.
$$
$endgroup$
We will use the identity
$$
binom{n}{k}binom{k}{r}=binom{n}{r}binom{n-r}{k-r}quad (ngeq kgeq rgeq 0).
$$
Interchange the order of summation and use the identity above to get that
$$
sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k}
=sum_{r=0}^{n}binom{n}{r}sum_{k=r}^{n}binom{n-r}{k-r}=sum_{r=0}^nbinom{n}{r}2^{n-r}=(1+2)^n=3^n
$$
where we used the fact that
$$
sum_{k=r}^{n}binom{n-r}{k-r}=sum_{u=0}^{n-r}binom{n-r}{u}=2^{n-r}.
$$
answered Dec 8 '18 at 19:22
Foobaz JohnFoobaz John
21.8k41352
21.8k41352
$begingroup$
Do you know a combinatorial proof of the statement?
$endgroup$
– nafhgood
Dec 8 '18 at 20:33
1
$begingroup$
@mathnoob I think I have a combinatorial argument, see my answer below.
$endgroup$
– Ned
Dec 8 '18 at 21:18
$begingroup$
That's cool! Thanks!
$endgroup$
– nafhgood
Dec 8 '18 at 21:22
add a comment |
$begingroup$
Do you know a combinatorial proof of the statement?
$endgroup$
– nafhgood
Dec 8 '18 at 20:33
1
$begingroup$
@mathnoob I think I have a combinatorial argument, see my answer below.
$endgroup$
– Ned
Dec 8 '18 at 21:18
$begingroup$
That's cool! Thanks!
$endgroup$
– nafhgood
Dec 8 '18 at 21:22
$begingroup$
Do you know a combinatorial proof of the statement?
$endgroup$
– nafhgood
Dec 8 '18 at 20:33
$begingroup$
Do you know a combinatorial proof of the statement?
$endgroup$
– nafhgood
Dec 8 '18 at 20:33
1
1
$begingroup$
@mathnoob I think I have a combinatorial argument, see my answer below.
$endgroup$
– Ned
Dec 8 '18 at 21:18
$begingroup$
@mathnoob I think I have a combinatorial argument, see my answer below.
$endgroup$
– Ned
Dec 8 '18 at 21:18
$begingroup$
That's cool! Thanks!
$endgroup$
– nafhgood
Dec 8 '18 at 21:22
$begingroup$
That's cool! Thanks!
$endgroup$
– nafhgood
Dec 8 '18 at 21:22
add a comment |
$begingroup$
Let $|X|=n$, so $3^n$ is the number of functions from $X$ to {$1,2,3$}.
Each such function corresponds uniquely to a pair of subsets $(A,B)$ with $A$ a subset of $B$ and $B$ a subset of $X$ by taking $B$ = {$x$ | $f(x)=2$ or $f(x)=3$} and $A$ = {$x$ | $f(x)=2$}.
The number of such pairs of nested subsets of $X$ is the double sum on the right hand side of the formula (where $k$ = $|B|$ and $r$ = $|A|$).
$endgroup$
add a comment |
$begingroup$
Let $|X|=n$, so $3^n$ is the number of functions from $X$ to {$1,2,3$}.
Each such function corresponds uniquely to a pair of subsets $(A,B)$ with $A$ a subset of $B$ and $B$ a subset of $X$ by taking $B$ = {$x$ | $f(x)=2$ or $f(x)=3$} and $A$ = {$x$ | $f(x)=2$}.
The number of such pairs of nested subsets of $X$ is the double sum on the right hand side of the formula (where $k$ = $|B|$ and $r$ = $|A|$).
$endgroup$
add a comment |
$begingroup$
Let $|X|=n$, so $3^n$ is the number of functions from $X$ to {$1,2,3$}.
Each such function corresponds uniquely to a pair of subsets $(A,B)$ with $A$ a subset of $B$ and $B$ a subset of $X$ by taking $B$ = {$x$ | $f(x)=2$ or $f(x)=3$} and $A$ = {$x$ | $f(x)=2$}.
The number of such pairs of nested subsets of $X$ is the double sum on the right hand side of the formula (where $k$ = $|B|$ and $r$ = $|A|$).
$endgroup$
Let $|X|=n$, so $3^n$ is the number of functions from $X$ to {$1,2,3$}.
Each such function corresponds uniquely to a pair of subsets $(A,B)$ with $A$ a subset of $B$ and $B$ a subset of $X$ by taking $B$ = {$x$ | $f(x)=2$ or $f(x)=3$} and $A$ = {$x$ | $f(x)=2$}.
The number of such pairs of nested subsets of $X$ is the double sum on the right hand side of the formula (where $k$ = $|B|$ and $r$ = $|A|$).
answered Dec 8 '18 at 21:11
NedNed
1,993910
1,993910
add a comment |
add a comment |
$begingroup$
You know that $displaystyle(1+x)^n=sum_{k=0}^nbinom nkx^k$
$displaystylesum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} =sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}=sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}1^r$
Since $displaystylesum_{r=0}^{k} binom{k}{r}1^r=(1+1)^k=2^k$, we have
$displaystyleimpliessum_{k=0}^{n} binom nk2^k=(1+2)^n=3^n$
$endgroup$
add a comment |
$begingroup$
You know that $displaystyle(1+x)^n=sum_{k=0}^nbinom nkx^k$
$displaystylesum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} =sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}=sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}1^r$
Since $displaystylesum_{r=0}^{k} binom{k}{r}1^r=(1+1)^k=2^k$, we have
$displaystyleimpliessum_{k=0}^{n} binom nk2^k=(1+2)^n=3^n$
$endgroup$
add a comment |
$begingroup$
You know that $displaystyle(1+x)^n=sum_{k=0}^nbinom nkx^k$
$displaystylesum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} =sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}=sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}1^r$
Since $displaystylesum_{r=0}^{k} binom{k}{r}1^r=(1+1)^k=2^k$, we have
$displaystyleimpliessum_{k=0}^{n} binom nk2^k=(1+2)^n=3^n$
$endgroup$
You know that $displaystyle(1+x)^n=sum_{k=0}^nbinom nkx^k$
$displaystylesum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r} binom{n}{k} =sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}=sum_{k=0}^{n}binom{n}{k}sum_{r=0}^{k} binom{k}{r}1^r$
Since $displaystylesum_{r=0}^{k} binom{k}{r}1^r=(1+1)^k=2^k$, we have
$displaystyleimpliessum_{k=0}^{n} binom nk2^k=(1+2)^n=3^n$
answered Dec 8 '18 at 19:31
Shubham JohriShubham Johri
4,992717
4,992717
add a comment |
add a comment |
$begingroup$
A convenient aspect is the index of the inner sum affects only one binomial coefficient. Setting parenthesis we might observe
begin{align*}
color{blue}{sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r}binom{n}{k}}
&=sum_{k=0}^{n}left(sum_{r=0}^{k} binom{k}{r} right)binom{n}{k}\
&=sum_{k=0}^{n}2^k binom{n}{k}\
&,,color{blue}{=3^n}
end{align*}
$endgroup$
add a comment |
$begingroup$
A convenient aspect is the index of the inner sum affects only one binomial coefficient. Setting parenthesis we might observe
begin{align*}
color{blue}{sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r}binom{n}{k}}
&=sum_{k=0}^{n}left(sum_{r=0}^{k} binom{k}{r} right)binom{n}{k}\
&=sum_{k=0}^{n}2^k binom{n}{k}\
&,,color{blue}{=3^n}
end{align*}
$endgroup$
add a comment |
$begingroup$
A convenient aspect is the index of the inner sum affects only one binomial coefficient. Setting parenthesis we might observe
begin{align*}
color{blue}{sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r}binom{n}{k}}
&=sum_{k=0}^{n}left(sum_{r=0}^{k} binom{k}{r} right)binom{n}{k}\
&=sum_{k=0}^{n}2^k binom{n}{k}\
&,,color{blue}{=3^n}
end{align*}
$endgroup$
A convenient aspect is the index of the inner sum affects only one binomial coefficient. Setting parenthesis we might observe
begin{align*}
color{blue}{sum_{k=0}^{n}sum_{r=0}^{k} binom{k}{r}binom{n}{k}}
&=sum_{k=0}^{n}left(sum_{r=0}^{k} binom{k}{r} right)binom{n}{k}\
&=sum_{k=0}^{n}2^k binom{n}{k}\
&,,color{blue}{=3^n}
end{align*}
answered Dec 9 '18 at 14:54
Markus ScheuerMarkus Scheuer
60.8k456145
60.8k456145
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%2f3031500%2fprove-the-identity-sum-k-0n-sum-r-0k-binomkr-binomnk-3n%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$
Use this question.
$endgroup$
– Dietrich Burde
Dec 8 '18 at 19:19
$begingroup$
You may be interested in the Multinomial theorem about multinomial coefficients.
$endgroup$
– Somos
Dec 8 '18 at 19:33