Algebraic proof of $sum_{i=0}^k{{n choose i}{m choose {k-i}}}= {{m+n}choose k}$
$begingroup$
I can't figure out an algebraic proof for the following identity:
$$sum_{i=0}^k{{n choose i}{m choose {k-i}}}= {{m+n}choose k}$$
Combinatorical solution:
We can see that as choosing some from $n$ and the rest of $k$ from $m$, thus $k$ in total.
Or we could just choose $k$ from the union.
combinatorics discrete-mathematics summation binomial-coefficients
edited Jan 10 at 3:02
Martin Sleziak
45k10122277
asked Sep 11 '13 at 17:08
NightRaNightRa
9991720
$endgroup$
add a comment |
$begingroup$
I can't figure out an algebraic proof for the following identity:
$$sum_{i=0}^k{{n choose i}{m choose {k-i}}}= {{m+n}choose k}$$
Combinatorical solution:
We can see that as choosing some from $n$ and the rest of $k$ from $m$, thus $k$ in total.
Or we could just choose $k$ from the union.
combinatorics discrete-mathematics summation binomial-coefficients
edited Jan 10 at 3:02
Martin Sleziak
45k10122277
asked Sep 11 '13 at 17:08
NightRaNightRa
9991720
$endgroup$
6
$begingroup$
For an algebraic proof (I don't know why you want one, to be honest), but consider the coefficient of $x^k$ in $(1+x)^n(1+x)^m = (1+x)^{n+m}$.
$endgroup$
– Andrew D
Sep 11 '13 at 17:11
$begingroup$
Its called the Chu-Vandermonde Identity, and there's already a post about it here: math.stackexchange.com/questions/219928/…
$endgroup$
– Salieri
Nov 23 '13 at 13:48
1
$begingroup$
@AndrewD: The algebraic proof does not depend on $n,m$ being natural numbers (but the binomial powers are now formal powers series); this is one reason why one might want an algebraic proof.
$endgroup$
– Marc van Leeuwen
Nov 23 '13 at 14:57
add a comment |
$begingroup$
I can't figure out an algebraic proof for the following identity:
$$sum_{i=0}^k{{n choose i}{m choose {k-i}}}= {{m+n}choose k}$$
Combinatorical solution:
We can see that as choosing some from $n$ and the rest of $k$ from $m$, thus $k$ in total.
Or we could just choose $k$ from the union.
combinatorics discrete-mathematics summation binomial-coefficients
edited Jan 10 at 3:02
Martin Sleziak
45k10122277
asked Sep 11 '13 at 17:08
NightRaNightRa
9991720
$endgroup$
I can't figure out an algebraic proof for the following identity:
$$sum_{i=0}^k{{n choose i}{m choose {k-i}}}= {{m+n}choose k}$$
Combinatorical solution:
We can see that as choosing some from $n$ and the rest of $k$ from $m$, thus $k$ in total.
Or we could just choose $k$ from the union.
combinatorics discrete-mathematics summation binomial-coefficients
combinatorics discrete-mathematics summation binomial-coefficients
edited Jan 10 at 3:02
Martin Sleziak
45k10122277
asked Sep 11 '13 at 17:08
NightRaNightRa
9991720
edited Jan 10 at 3:02
Martin Sleziak
45k10122277
asked Sep 11 '13 at 17:08
NightRaNightRa
9991720
edited Jan 10 at 3:02
Martin Sleziak
45k10122277
edited Jan 10 at 3:02
Martin Sleziak
45k10122277
edited Jan 10 at 3:02
Martin Sleziak
45k10122277
45k10122277
asked Sep 11 '13 at 17:08
NightRaNightRa
9991720
asked Sep 11 '13 at 17:08
NightRaNightRa
9991720
asked Sep 11 '13 at 17:08
NightRaNightRa
9991720
9991720
6
$begingroup$
For an algebraic proof (I don't know why you want one, to be honest), but consider the coefficient of $x^k$ in $(1+x)^n(1+x)^m = (1+x)^{n+m}$.
$endgroup$
– Andrew D
Sep 11 '13 at 17:11
$begingroup$
Its called the Chu-Vandermonde Identity, and there's already a post about it here: math.stackexchange.com/questions/219928/…
$endgroup$
– Salieri
Nov 23 '13 at 13:48
1
$begingroup$
@AndrewD: The algebraic proof does not depend on $n,m$ being natural numbers (but the binomial powers are now formal powers series); this is one reason why one might want an algebraic proof.
$endgroup$
– Marc van Leeuwen
Nov 23 '13 at 14:57
add a comment |
6
$begingroup$
For an algebraic proof (I don't know why you want one, to be honest), but consider the coefficient of $x^k$ in $(1+x)^n(1+x)^m = (1+x)^{n+m}$.
$endgroup$
– Andrew D
Sep 11 '13 at 17:11
$begingroup$
Its called the Chu-Vandermonde Identity, and there's already a post about it here: math.stackexchange.com/questions/219928/…
$endgroup$
– Salieri
Nov 23 '13 at 13:48
1
$begingroup$
@AndrewD: The algebraic proof does not depend on $n,m$ being natural numbers (but the binomial powers are now formal powers series); this is one reason why one might want an algebraic proof.
$endgroup$
– Marc van Leeuwen
Nov 23 '13 at 14:57
6
6
$begingroup$
For an algebraic proof (I don't know why you want one, to be honest), but consider the coefficient of $x^k$ in $(1+x)^n(1+x)^m = (1+x)^{n+m}$.
$endgroup$
– Andrew D
Sep 11 '13 at 17:11
$begingroup$
For an algebraic proof (I don't know why you want one, to be honest), but consider the coefficient of $x^k$ in $(1+x)^n(1+x)^m = (1+x)^{n+m}$.
$endgroup$
– Andrew D
Sep 11 '13 at 17:11
$begingroup$
Its called the Chu-Vandermonde Identity, and there's already a post about it here: math.stackexchange.com/questions/219928/…
$endgroup$
– Salieri
Nov 23 '13 at 13:48
$begingroup$
Its called the Chu-Vandermonde Identity, and there's already a post about it here: math.stackexchange.com/questions/219928/…
$endgroup$
– Salieri
Nov 23 '13 at 13:48
1
1
$begingroup$
@AndrewD: The algebraic proof does not depend on $n,m$ being natural numbers (but the binomial powers are now formal powers series); this is one reason why one might want an algebraic proof.
$endgroup$
– Marc van Leeuwen
Nov 23 '13 at 14:57
$begingroup$
@AndrewD: The algebraic proof does not depend on $n,m$ being natural numbers (but the binomial powers are now formal powers series); this is one reason why one might want an algebraic proof.
$endgroup$
– Marc van Leeuwen
Nov 23 '13 at 14:57
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
For identities involving binomial coefficients sometimes "combinatorial proofs" and "algebraic proofs" are offered. Here we have two proofs for the Vandermonde Convolution:
Algebraic proof: The sum of the LHS of the convolution formula equals the coefficient of $x^k$ on the LHS of the polynomial
$$
(1+x)^n(1+x)^m=(1+x)^{m+n}.
$$
The binomial coefficient on the RHS of the convolutions formula equals the coefficient of $x^k$ on the RHS of the polynomial equation.Combinatorial proof: Suppose that there are $n+m$ objects in a set, $n$ of them white and $m$ of them black. There are $binom{n+m}{k}$ ways to choose $k$ elements in all. This is the RHS. The number of ways to choose $j$ white and $k-j$ black objects is the product $binom{n}{j}binom{m}{k-j}$, so the sum of all these objects, the LHS, must be the same total as on the RHS.
answered Sep 11 '13 at 18:39
Dietrich BurdeDietrich Burde
81.7k648106
$endgroup$
add a comment |
$begingroup$
Using the binomial theorem consider $$sum_{k=0}^{m+n}{m+nchoose k}x^k=(1+x)^{m+n}.$$ The right-hand side becomes $$(1+x)^m(1+x)^n=(sum_{r=0}^m{mchoose r}x^r)(sum_{s=0}^n{nchoose s}x^s).$$ The product of the two polynomials on the right-hand side can be rewritten as $$sum_{k=0}^{m+n}(sum_{i=0}^k{nchoose i}{mchoose k-i})x^r.$$ Thus $$sum_{i=0}^k{nchoose i}{mchoose k-i}={m+nchoose k}.$$
answered Nov 23 '13 at 14:03
1233dfv1233dfv
4,1931326
$endgroup$
add a comment |
$begingroup$
For another proof, see the First Proof of Theorem 3.29 in my Notes on the combinatorial fundamentals of algebra. (NB: It is Theorem 3.29 in the version of 10 January 2019. Theorem labels are subject to change, so search for "Chu-Vandermonde identity" if Theorem 3.29 is something different in your version.) This is not a particularly enlightening proof, but it has the advantage of requiring the least about $n$ and $m$: it works when $n$ and $m$ are elements of a commutative $mathbb{Q}$-algebra. (Compare to the combinatorial proof, which requires $n$ and $m$ to be nonnegative integers. Compare also to the proof using the binomial formula, which works generally only if one has an algebraic way of proving $left(1+xright)^nleft(1+xright)^m = left(1+xright)^{n+m}$ for non-integer $n$ and $m$.)
This has been linked from How do i prove that $sumlimits_{r=0}^k binom{m}{r}binom{n}{k-r} = binom{m+n}{k}$ , which has other proofs.
answered Jul 24 '15 at 20:14
darij grinbergdarij grinberg
11.5k33168
$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%2f490741%2falgebraic-proof-of-sum-i-0kn-choose-im-choose-k-i-mn-choose%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
For identities involving binomial coefficients sometimes "combinatorial proofs" and "algebraic proofs" are offered. Here we have two proofs for the Vandermonde Convolution:
Algebraic proof: The sum of the LHS of the convolution formula equals the coefficient of $x^k$ on the LHS of the polynomial
$$
(1+x)^n(1+x)^m=(1+x)^{m+n}.
$$
The binomial coefficient on the RHS of the convolutions formula equals the coefficient of $x^k$ on the RHS of the polynomial equation.Combinatorial proof: Suppose that there are $n+m$ objects in a set, $n$ of them white and $m$ of them black. There are $binom{n+m}{k}$ ways to choose $k$ elements in all. This is the RHS. The number of ways to choose $j$ white and $k-j$ black objects is the product $binom{n}{j}binom{m}{k-j}$, so the sum of all these objects, the LHS, must be the same total as on the RHS.
answered Sep 11 '13 at 18:39
Dietrich BurdeDietrich Burde
81.7k648106
$endgroup$
add a comment |
$begingroup$
For identities involving binomial coefficients sometimes "combinatorial proofs" and "algebraic proofs" are offered. Here we have two proofs for the Vandermonde Convolution:
Algebraic proof: The sum of the LHS of the convolution formula equals the coefficient of $x^k$ on the LHS of the polynomial
$$
(1+x)^n(1+x)^m=(1+x)^{m+n}.
$$
The binomial coefficient on the RHS of the convolutions formula equals the coefficient of $x^k$ on the RHS of the polynomial equation.Combinatorial proof: Suppose that there are $n+m$ objects in a set, $n$ of them white and $m$ of them black. There are $binom{n+m}{k}$ ways to choose $k$ elements in all. This is the RHS. The number of ways to choose $j$ white and $k-j$ black objects is the product $binom{n}{j}binom{m}{k-j}$, so the sum of all these objects, the LHS, must be the same total as on the RHS.
answered Sep 11 '13 at 18:39
Dietrich BurdeDietrich Burde
81.7k648106
$endgroup$
add a comment |
$begingroup$
For identities involving binomial coefficients sometimes "combinatorial proofs" and "algebraic proofs" are offered. Here we have two proofs for the Vandermonde Convolution:
Algebraic proof: The sum of the LHS of the convolution formula equals the coefficient of $x^k$ on the LHS of the polynomial
$$
(1+x)^n(1+x)^m=(1+x)^{m+n}.
$$
The binomial coefficient on the RHS of the convolutions formula equals the coefficient of $x^k$ on the RHS of the polynomial equation.Combinatorial proof: Suppose that there are $n+m$ objects in a set, $n$ of them white and $m$ of them black. There are $binom{n+m}{k}$ ways to choose $k$ elements in all. This is the RHS. The number of ways to choose $j$ white and $k-j$ black objects is the product $binom{n}{j}binom{m}{k-j}$, so the sum of all these objects, the LHS, must be the same total as on the RHS.
answered Sep 11 '13 at 18:39
Dietrich BurdeDietrich Burde
81.7k648106
$endgroup$
For identities involving binomial coefficients sometimes "combinatorial proofs" and "algebraic proofs" are offered. Here we have two proofs for the Vandermonde Convolution:
Algebraic proof: The sum of the LHS of the convolution formula equals the coefficient of $x^k$ on the LHS of the polynomial
$$
(1+x)^n(1+x)^m=(1+x)^{m+n}.
$$
The binomial coefficient on the RHS of the convolutions formula equals the coefficient of $x^k$ on the RHS of the polynomial equation.Combinatorial proof: Suppose that there are $n+m$ objects in a set, $n$ of them white and $m$ of them black. There are $binom{n+m}{k}$ ways to choose $k$ elements in all. This is the RHS. The number of ways to choose $j$ white and $k-j$ black objects is the product $binom{n}{j}binom{m}{k-j}$, so the sum of all these objects, the LHS, must be the same total as on the RHS.
answered Sep 11 '13 at 18:39
Dietrich BurdeDietrich Burde
81.7k648106
answered Sep 11 '13 at 18:39
Dietrich BurdeDietrich Burde
81.7k648106
answered Sep 11 '13 at 18:39
Dietrich BurdeDietrich Burde
81.7k648106
answered Sep 11 '13 at 18:39
Dietrich BurdeDietrich Burde
81.7k648106
81.7k648106
add a comment |
add a comment |
$begingroup$
Using the binomial theorem consider $$sum_{k=0}^{m+n}{m+nchoose k}x^k=(1+x)^{m+n}.$$ The right-hand side becomes $$(1+x)^m(1+x)^n=(sum_{r=0}^m{mchoose r}x^r)(sum_{s=0}^n{nchoose s}x^s).$$ The product of the two polynomials on the right-hand side can be rewritten as $$sum_{k=0}^{m+n}(sum_{i=0}^k{nchoose i}{mchoose k-i})x^r.$$ Thus $$sum_{i=0}^k{nchoose i}{mchoose k-i}={m+nchoose k}.$$
answered Nov 23 '13 at 14:03
1233dfv1233dfv
4,1931326
$endgroup$
add a comment |
$begingroup$
Using the binomial theorem consider $$sum_{k=0}^{m+n}{m+nchoose k}x^k=(1+x)^{m+n}.$$ The right-hand side becomes $$(1+x)^m(1+x)^n=(sum_{r=0}^m{mchoose r}x^r)(sum_{s=0}^n{nchoose s}x^s).$$ The product of the two polynomials on the right-hand side can be rewritten as $$sum_{k=0}^{m+n}(sum_{i=0}^k{nchoose i}{mchoose k-i})x^r.$$ Thus $$sum_{i=0}^k{nchoose i}{mchoose k-i}={m+nchoose k}.$$
answered Nov 23 '13 at 14:03
1233dfv1233dfv
4,1931326
$endgroup$
add a comment |
$begingroup$
Using the binomial theorem consider $$sum_{k=0}^{m+n}{m+nchoose k}x^k=(1+x)^{m+n}.$$ The right-hand side becomes $$(1+x)^m(1+x)^n=(sum_{r=0}^m{mchoose r}x^r)(sum_{s=0}^n{nchoose s}x^s).$$ The product of the two polynomials on the right-hand side can be rewritten as $$sum_{k=0}^{m+n}(sum_{i=0}^k{nchoose i}{mchoose k-i})x^r.$$ Thus $$sum_{i=0}^k{nchoose i}{mchoose k-i}={m+nchoose k}.$$
answered Nov 23 '13 at 14:03
1233dfv1233dfv
4,1931326
$endgroup$
Using the binomial theorem consider $$sum_{k=0}^{m+n}{m+nchoose k}x^k=(1+x)^{m+n}.$$ The right-hand side becomes $$(1+x)^m(1+x)^n=(sum_{r=0}^m{mchoose r}x^r)(sum_{s=0}^n{nchoose s}x^s).$$ The product of the two polynomials on the right-hand side can be rewritten as $$sum_{k=0}^{m+n}(sum_{i=0}^k{nchoose i}{mchoose k-i})x^r.$$ Thus $$sum_{i=0}^k{nchoose i}{mchoose k-i}={m+nchoose k}.$$
answered Nov 23 '13 at 14:03
1233dfv1233dfv
4,1931326
edited Nov 26 '13 at 22:40
answered Nov 23 '13 at 14:03
1233dfv1233dfv
4,1931326
answered Nov 23 '13 at 14:03
1233dfv1233dfv
4,1931326
answered Nov 23 '13 at 14:03
1233dfv1233dfv
4,1931326
4,1931326
add a comment |
add a comment |
$begingroup$
For another proof, see the First Proof of Theorem 3.29 in my Notes on the combinatorial fundamentals of algebra. (NB: It is Theorem 3.29 in the version of 10 January 2019. Theorem labels are subject to change, so search for "Chu-Vandermonde identity" if Theorem 3.29 is something different in your version.) This is not a particularly enlightening proof, but it has the advantage of requiring the least about $n$ and $m$: it works when $n$ and $m$ are elements of a commutative $mathbb{Q}$-algebra. (Compare to the combinatorial proof, which requires $n$ and $m$ to be nonnegative integers. Compare also to the proof using the binomial formula, which works generally only if one has an algebraic way of proving $left(1+xright)^nleft(1+xright)^m = left(1+xright)^{n+m}$ for non-integer $n$ and $m$.)
This has been linked from How do i prove that $sumlimits_{r=0}^k binom{m}{r}binom{n}{k-r} = binom{m+n}{k}$ , which has other proofs.
answered Jul 24 '15 at 20:14
darij grinbergdarij grinberg
11.5k33168
$endgroup$
add a comment |
$begingroup$
For another proof, see the First Proof of Theorem 3.29 in my Notes on the combinatorial fundamentals of algebra. (NB: It is Theorem 3.29 in the version of 10 January 2019. Theorem labels are subject to change, so search for "Chu-Vandermonde identity" if Theorem 3.29 is something different in your version.) This is not a particularly enlightening proof, but it has the advantage of requiring the least about $n$ and $m$: it works when $n$ and $m$ are elements of a commutative $mathbb{Q}$-algebra. (Compare to the combinatorial proof, which requires $n$ and $m$ to be nonnegative integers. Compare also to the proof using the binomial formula, which works generally only if one has an algebraic way of proving $left(1+xright)^nleft(1+xright)^m = left(1+xright)^{n+m}$ for non-integer $n$ and $m$.)
This has been linked from How do i prove that $sumlimits_{r=0}^k binom{m}{r}binom{n}{k-r} = binom{m+n}{k}$ , which has other proofs.
answered Jul 24 '15 at 20:14
darij grinbergdarij grinberg
11.5k33168
$endgroup$
add a comment |
$begingroup$
For another proof, see the First Proof of Theorem 3.29 in my Notes on the combinatorial fundamentals of algebra. (NB: It is Theorem 3.29 in the version of 10 January 2019. Theorem labels are subject to change, so search for "Chu-Vandermonde identity" if Theorem 3.29 is something different in your version.) This is not a particularly enlightening proof, but it has the advantage of requiring the least about $n$ and $m$: it works when $n$ and $m$ are elements of a commutative $mathbb{Q}$-algebra. (Compare to the combinatorial proof, which requires $n$ and $m$ to be nonnegative integers. Compare also to the proof using the binomial formula, which works generally only if one has an algebraic way of proving $left(1+xright)^nleft(1+xright)^m = left(1+xright)^{n+m}$ for non-integer $n$ and $m$.)
This has been linked from How do i prove that $sumlimits_{r=0}^k binom{m}{r}binom{n}{k-r} = binom{m+n}{k}$ , which has other proofs.
answered Jul 24 '15 at 20:14
darij grinbergdarij grinberg
11.5k33168
$endgroup$
For another proof, see the First Proof of Theorem 3.29 in my Notes on the combinatorial fundamentals of algebra. (NB: It is Theorem 3.29 in the version of 10 January 2019. Theorem labels are subject to change, so search for "Chu-Vandermonde identity" if Theorem 3.29 is something different in your version.) This is not a particularly enlightening proof, but it has the advantage of requiring the least about $n$ and $m$: it works when $n$ and $m$ are elements of a commutative $mathbb{Q}$-algebra. (Compare to the combinatorial proof, which requires $n$ and $m$ to be nonnegative integers. Compare also to the proof using the binomial formula, which works generally only if one has an algebraic way of proving $left(1+xright)^nleft(1+xright)^m = left(1+xright)^{n+m}$ for non-integer $n$ and $m$.)
This has been linked from How do i prove that $sumlimits_{r=0}^k binom{m}{r}binom{n}{k-r} = binom{m+n}{k}$ , which has other proofs.
answered Jul 24 '15 at 20:14
darij grinbergdarij grinberg
11.5k33168
edited Jan 10 at 1:49
answered Jul 24 '15 at 20:14
darij grinbergdarij grinberg
11.5k33168
answered Jul 24 '15 at 20:14
darij grinbergdarij grinberg
11.5k33168
answered Jul 24 '15 at 20:14
darij grinbergdarij grinberg
11.5k33168
11.5k33168
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%2f490741%2falgebraic-proof-of-sum-i-0kn-choose-im-choose-k-i-mn-choose%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
6
$begingroup$
For an algebraic proof (I don't know why you want one, to be honest), but consider the coefficient of $x^k$ in $(1+x)^n(1+x)^m = (1+x)^{n+m}$.
$endgroup$
– Andrew D
Sep 11 '13 at 17:11
$begingroup$
Its called the Chu-Vandermonde Identity, and there's already a post about it here: math.stackexchange.com/questions/219928/…
$endgroup$
– Salieri
Nov 23 '13 at 13:48
1
$begingroup$
@AndrewD: The algebraic proof does not depend on $n,m$ being natural numbers (but the binomial powers are now formal powers series); this is one reason why one might want an algebraic proof.
$endgroup$
– Marc van Leeuwen
Nov 23 '13 at 14:57