Mixing
Is there an algebraic proof for $sum_{m=k}^{n-k} binom{m}{k}binom{n-m}{k} = binom{n+1}{2k+1}, nge2kge0$
$begingroup$
$sum_{m=k}^{n-k} binom{m}{k}binom{n-m}{k} = binom{n+1}{2k+1}, nge2kge0$
An combinatorial proof of the identity above states as follow:
(1)Number of ways of picking (2k+1) numbers from 1 to (n+1) should be $binom{n+1}{2k+1}$
(2)We pick (2k+1) numbers from 1 to (n+1) with median value (m+1). Then, k numbers must be selected from 1~m, and the other k numbers must be chosen from (m+2)~(n+1). Thus there are $binom{m}{k}binom{n-m}{k}$ ways for picking (2k+1) numbers with median value (m+1). Since $n-kge mge k$, there are total $sum_{m=k}^{n-k} binom{m}{k}binom{n-m}{k}$ ways.
Since (1)=(2), the statement is true.
But is it possible to sketch an algebraic proof that doesn't require building combinatorial models?
combinatorics binomial-coefficients combinatorial-proofs
asked Jan 1 '18 at 11:19
user3737735user3737735
161
$endgroup$
add a comment |
$begingroup$
$sum_{m=k}^{n-k} binom{m}{k}binom{n-m}{k} = binom{n+1}{2k+1}, nge2kge0$
An combinatorial proof of the identity above states as follow:
(1)Number of ways of picking (2k+1) numbers from 1 to (n+1) should be $binom{n+1}{2k+1}$
(2)We pick (2k+1) numbers from 1 to (n+1) with median value (m+1). Then, k numbers must be selected from 1~m, and the other k numbers must be chosen from (m+2)~(n+1). Thus there are $binom{m}{k}binom{n-m}{k}$ ways for picking (2k+1) numbers with median value (m+1). Since $n-kge mge k$, there are total $sum_{m=k}^{n-k} binom{m}{k}binom{n-m}{k}$ ways.
Since (1)=(2), the statement is true.
But is it possible to sketch an algebraic proof that doesn't require building combinatorial models?
combinatorics binomial-coefficients combinatorial-proofs
asked Jan 1 '18 at 11:19
user3737735user3737735
161
$endgroup$
$begingroup$
Consider coefficient of $x^{n}$ in $[x^k(1-x)^{k+1}][x^k(1-x)^{k+1}]$.
$endgroup$
– Lord Shark the Unknown
Jan 1 '18 at 11:22
add a comment |
$begingroup$
$sum_{m=k}^{n-k} binom{m}{k}binom{n-m}{k} = binom{n+1}{2k+1}, nge2kge0$
An combinatorial proof of the identity above states as follow:
(1)Number of ways of picking (2k+1) numbers from 1 to (n+1) should be $binom{n+1}{2k+1}$
(2)We pick (2k+1) numbers from 1 to (n+1) with median value (m+1). Then, k numbers must be selected from 1~m, and the other k numbers must be chosen from (m+2)~(n+1). Thus there are $binom{m}{k}binom{n-m}{k}$ ways for picking (2k+1) numbers with median value (m+1). Since $n-kge mge k$, there are total $sum_{m=k}^{n-k} binom{m}{k}binom{n-m}{k}$ ways.
Since (1)=(2), the statement is true.
But is it possible to sketch an algebraic proof that doesn't require building combinatorial models?
combinatorics binomial-coefficients combinatorial-proofs
asked Jan 1 '18 at 11:19
user3737735user3737735
161
$endgroup$
$sum_{m=k}^{n-k} binom{m}{k}binom{n-m}{k} = binom{n+1}{2k+1}, nge2kge0$
An combinatorial proof of the identity above states as follow:
(1)Number of ways of picking (2k+1) numbers from 1 to (n+1) should be $binom{n+1}{2k+1}$
(2)We pick (2k+1) numbers from 1 to (n+1) with median value (m+1). Then, k numbers must be selected from 1~m, and the other k numbers must be chosen from (m+2)~(n+1). Thus there are $binom{m}{k}binom{n-m}{k}$ ways for picking (2k+1) numbers with median value (m+1). Since $n-kge mge k$, there are total $sum_{m=k}^{n-k} binom{m}{k}binom{n-m}{k}$ ways.
Since (1)=(2), the statement is true.
But is it possible to sketch an algebraic proof that doesn't require building combinatorial models?
combinatorics binomial-coefficients combinatorial-proofs
combinatorics binomial-coefficients combinatorial-proofs
asked Jan 1 '18 at 11:19
user3737735user3737735
161
asked Jan 1 '18 at 11:19
user3737735user3737735
161
asked Jan 1 '18 at 11:19
user3737735user3737735
161
asked Jan 1 '18 at 11:19
user3737735user3737735
161
asked Jan 1 '18 at 11:19
user3737735user3737735
161
161
$begingroup$
Consider coefficient of $x^{n}$ in $[x^k(1-x)^{k+1}][x^k(1-x)^{k+1}]$.
$endgroup$
– Lord Shark the Unknown
Jan 1 '18 at 11:22
add a comment |
$begingroup$
Consider coefficient of $x^{n}$ in $[x^k(1-x)^{k+1}][x^k(1-x)^{k+1}]$.
$endgroup$
– Lord Shark the Unknown
Jan 1 '18 at 11:22
$begingroup$
Consider coefficient of $x^{n}$ in $[x^k(1-x)^{k+1}][x^k(1-x)^{k+1}]$.
$endgroup$
– Lord Shark the Unknown
Jan 1 '18 at 11:22
$begingroup$
Consider coefficient of $x^{n}$ in $[x^k(1-x)^{k+1}][x^k(1-x)^{k+1}]$.
$endgroup$
– Lord Shark the Unknown
Jan 1 '18 at 11:22
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here is an algebraic proof based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance
begin{align*}
[z^k](1+z)^n=binom{n}{k}
end{align*}
We obtain
begin{align*}
color{blue}{sum_{m=k}^{n-k}}&color{blue}{binom{m}{k}binom{n-m}{k}}\
&=sum_{m=0}^{n-2k}binom{m+k}{m}binom{n-m-k}{k}tag{1}\
&=sum_{m=0}^{n-2k}binom{-k-1}{m}(-1)^mbinom{n-m-k}{k}tag{2}\
&=sum_{m=0}^infty[z^m](1-z)^{-k-1}[u^k](1+u)^{n-m-k}tag{3}\
&=[u^k](1+u)^{n-k}sum_{m=0}^inftyleft(frac{1}{1+u}right)^{m}[z^m](1-z)^{-k-1}tag{4}\
&=[u^k](1+u)^{n-k}left(1-frac{1}{1+u}right)^{-k-1}tag{5}\
&=[u^k](1+u)^{n-k}u^{-k-1}(1+u)^{k+1}tag{6}\
&=[u^{2k+1}](1+u)^{n+1}tag{7}\
&color{blue}{=binom{n+1}{2k+1}}tag{8}
end{align*}
and the claim follows.
Comment:
In (1) we shift the index to start with $m=0$ and use the binomial identity $binom{p}{q}=binom{p}{p-q}$.
In (2) we use the binomial identity $binom{-p}{q}=binom{p+q-1}{q}(-1)^q$.
In (3) we apply the coefficient of operator twice and we set the upper bound of the series to $infty$ without changing anything since we are adding zeros only.
In (4) we use the linearity of the coefficient of operator and we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.
In (5) we apply the substitution rule of the coefficient of operator with $z=frac{1}{1+u}$
begin{align*}
A(u)=sum_{m=0}^infty a_m u^m=sum_{m=0}^infty u^m [z^m]A(z)
end{align*}In (6) we do some simplifications.
In (7) we do some more simplifications and apply the same rule as we did in (4).
In (8) we select the coefficient of $u^{2k+1}$.
answered Jan 1 '18 at 19:25
Markus ScheuerMarkus Scheuer
61.3k456146
$endgroup$
add a comment |
$begingroup$
More generally:
Theorem 1. For every nonnegative integers $x$, $y$ and $n$, we have
begin{equation}
dbinom{n+1}{x+y+1}=sum_{m=0}^{n}dbinom{m}{x}dbinom{n-m}{y}.
end{equation}
This equality rewrites as
begin{equation}
dbinom{n+1}{x+y+1} = sum_{m=x}^{n-y} dbinom{m}{x}dbinom{n-m}{y} ,
end{equation}
because all addends $dbinom{m}{x}dbinom{n-m}{y}$ are zero except for those where $x leq m leq n-y$.
Your identity is the particular case of the latter equality for $x = k$ and $y = k$.
Your nice bijective proof of the original identity can easily be generalized to a proof of Theorem 1; just count all ways of picking an $left(x+y+1right)$-element subset of $left{1,2,ldots,n+1right}$ according to the value of the $left(x+1right)$-th-lowest element of the subset. Indeed, for any given $m in left{0,1,ldots,nright}$, picking an $left(x+y+1right)$-element subset $S$ of $left{1,2,ldots,n+1right}$ whose $left(x+1right)$-th-lowest element is $m+1$ is tantamount to picking an $x$-element subset of $left{1,2,ldots,mright}$ (which will contain the $x$ elements of $S$ lower than $m+1$) and picking a $y$-element subset of $left{m+2,m+3,ldots,n+1right}$ (which will contain the $y$ elements of $S$ higher than $m+1$). This gives $dbinom{m}{x}dbinom{n-m}{y}$ for the number of choices.
As for other proofs:
An elementary proof is given in Proposition 3.32 (f) in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, Version of 10 January 2019. The proposition is obtained from Vandermonde convolution by several applications of upper negation.
Theorem 1 is also equivalent to the identity proven in Proof of $sum_{m=0}^{n}binom{m}{j}binom{n-m}{k-j}=binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity) (just set $j = x$ and $k = x+y$); the proof uses generating functions.
answered Jan 1 '18 at 12:21
darij grinbergdarij grinberg
10.8k33062
$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%2f2587436%2fis-there-an-algebraic-proof-for-sum-m-kn-k-binommk-binomn-mk%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$
Here is an algebraic proof based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance
begin{align*}
[z^k](1+z)^n=binom{n}{k}
end{align*}
We obtain
begin{align*}
color{blue}{sum_{m=k}^{n-k}}&color{blue}{binom{m}{k}binom{n-m}{k}}\
&=sum_{m=0}^{n-2k}binom{m+k}{m}binom{n-m-k}{k}tag{1}\
&=sum_{m=0}^{n-2k}binom{-k-1}{m}(-1)^mbinom{n-m-k}{k}tag{2}\
&=sum_{m=0}^infty[z^m](1-z)^{-k-1}[u^k](1+u)^{n-m-k}tag{3}\
&=[u^k](1+u)^{n-k}sum_{m=0}^inftyleft(frac{1}{1+u}right)^{m}[z^m](1-z)^{-k-1}tag{4}\
&=[u^k](1+u)^{n-k}left(1-frac{1}{1+u}right)^{-k-1}tag{5}\
&=[u^k](1+u)^{n-k}u^{-k-1}(1+u)^{k+1}tag{6}\
&=[u^{2k+1}](1+u)^{n+1}tag{7}\
&color{blue}{=binom{n+1}{2k+1}}tag{8}
end{align*}
and the claim follows.
Comment:
In (1) we shift the index to start with $m=0$ and use the binomial identity $binom{p}{q}=binom{p}{p-q}$.
In (2) we use the binomial identity $binom{-p}{q}=binom{p+q-1}{q}(-1)^q$.
In (3) we apply the coefficient of operator twice and we set the upper bound of the series to $infty$ without changing anything since we are adding zeros only.
In (4) we use the linearity of the coefficient of operator and we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.
In (5) we apply the substitution rule of the coefficient of operator with $z=frac{1}{1+u}$
begin{align*}
A(u)=sum_{m=0}^infty a_m u^m=sum_{m=0}^infty u^m [z^m]A(z)
end{align*}In (6) we do some simplifications.
In (7) we do some more simplifications and apply the same rule as we did in (4).
In (8) we select the coefficient of $u^{2k+1}$.
answered Jan 1 '18 at 19:25
Markus ScheuerMarkus Scheuer
61.3k456146
$endgroup$
add a comment |
$begingroup$
Here is an algebraic proof based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance
begin{align*}
[z^k](1+z)^n=binom{n}{k}
end{align*}
We obtain
begin{align*}
color{blue}{sum_{m=k}^{n-k}}&color{blue}{binom{m}{k}binom{n-m}{k}}\
&=sum_{m=0}^{n-2k}binom{m+k}{m}binom{n-m-k}{k}tag{1}\
&=sum_{m=0}^{n-2k}binom{-k-1}{m}(-1)^mbinom{n-m-k}{k}tag{2}\
&=sum_{m=0}^infty[z^m](1-z)^{-k-1}[u^k](1+u)^{n-m-k}tag{3}\
&=[u^k](1+u)^{n-k}sum_{m=0}^inftyleft(frac{1}{1+u}right)^{m}[z^m](1-z)^{-k-1}tag{4}\
&=[u^k](1+u)^{n-k}left(1-frac{1}{1+u}right)^{-k-1}tag{5}\
&=[u^k](1+u)^{n-k}u^{-k-1}(1+u)^{k+1}tag{6}\
&=[u^{2k+1}](1+u)^{n+1}tag{7}\
&color{blue}{=binom{n+1}{2k+1}}tag{8}
end{align*}
and the claim follows.
Comment:
In (1) we shift the index to start with $m=0$ and use the binomial identity $binom{p}{q}=binom{p}{p-q}$.
In (2) we use the binomial identity $binom{-p}{q}=binom{p+q-1}{q}(-1)^q$.
In (3) we apply the coefficient of operator twice and we set the upper bound of the series to $infty$ without changing anything since we are adding zeros only.
In (4) we use the linearity of the coefficient of operator and we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.
In (5) we apply the substitution rule of the coefficient of operator with $z=frac{1}{1+u}$
begin{align*}
A(u)=sum_{m=0}^infty a_m u^m=sum_{m=0}^infty u^m [z^m]A(z)
end{align*}In (6) we do some simplifications.
In (7) we do some more simplifications and apply the same rule as we did in (4).
In (8) we select the coefficient of $u^{2k+1}$.
answered Jan 1 '18 at 19:25
Markus ScheuerMarkus Scheuer
61.3k456146
$endgroup$
add a comment |
$begingroup$
Here is an algebraic proof based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance
begin{align*}
[z^k](1+z)^n=binom{n}{k}
end{align*}
We obtain
begin{align*}
color{blue}{sum_{m=k}^{n-k}}&color{blue}{binom{m}{k}binom{n-m}{k}}\
&=sum_{m=0}^{n-2k}binom{m+k}{m}binom{n-m-k}{k}tag{1}\
&=sum_{m=0}^{n-2k}binom{-k-1}{m}(-1)^mbinom{n-m-k}{k}tag{2}\
&=sum_{m=0}^infty[z^m](1-z)^{-k-1}[u^k](1+u)^{n-m-k}tag{3}\
&=[u^k](1+u)^{n-k}sum_{m=0}^inftyleft(frac{1}{1+u}right)^{m}[z^m](1-z)^{-k-1}tag{4}\
&=[u^k](1+u)^{n-k}left(1-frac{1}{1+u}right)^{-k-1}tag{5}\
&=[u^k](1+u)^{n-k}u^{-k-1}(1+u)^{k+1}tag{6}\
&=[u^{2k+1}](1+u)^{n+1}tag{7}\
&color{blue}{=binom{n+1}{2k+1}}tag{8}
end{align*}
and the claim follows.
Comment:
In (1) we shift the index to start with $m=0$ and use the binomial identity $binom{p}{q}=binom{p}{p-q}$.
In (2) we use the binomial identity $binom{-p}{q}=binom{p+q-1}{q}(-1)^q$.
In (3) we apply the coefficient of operator twice and we set the upper bound of the series to $infty$ without changing anything since we are adding zeros only.
In (4) we use the linearity of the coefficient of operator and we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.
In (5) we apply the substitution rule of the coefficient of operator with $z=frac{1}{1+u}$
begin{align*}
A(u)=sum_{m=0}^infty a_m u^m=sum_{m=0}^infty u^m [z^m]A(z)
end{align*}In (6) we do some simplifications.
In (7) we do some more simplifications and apply the same rule as we did in (4).
In (8) we select the coefficient of $u^{2k+1}$.
answered Jan 1 '18 at 19:25
Markus ScheuerMarkus Scheuer
61.3k456146
$endgroup$
Here is an algebraic proof based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance
begin{align*}
[z^k](1+z)^n=binom{n}{k}
end{align*}
We obtain
begin{align*}
color{blue}{sum_{m=k}^{n-k}}&color{blue}{binom{m}{k}binom{n-m}{k}}\
&=sum_{m=0}^{n-2k}binom{m+k}{m}binom{n-m-k}{k}tag{1}\
&=sum_{m=0}^{n-2k}binom{-k-1}{m}(-1)^mbinom{n-m-k}{k}tag{2}\
&=sum_{m=0}^infty[z^m](1-z)^{-k-1}[u^k](1+u)^{n-m-k}tag{3}\
&=[u^k](1+u)^{n-k}sum_{m=0}^inftyleft(frac{1}{1+u}right)^{m}[z^m](1-z)^{-k-1}tag{4}\
&=[u^k](1+u)^{n-k}left(1-frac{1}{1+u}right)^{-k-1}tag{5}\
&=[u^k](1+u)^{n-k}u^{-k-1}(1+u)^{k+1}tag{6}\
&=[u^{2k+1}](1+u)^{n+1}tag{7}\
&color{blue}{=binom{n+1}{2k+1}}tag{8}
end{align*}
and the claim follows.
Comment:
In (1) we shift the index to start with $m=0$ and use the binomial identity $binom{p}{q}=binom{p}{p-q}$.
In (2) we use the binomial identity $binom{-p}{q}=binom{p+q-1}{q}(-1)^q$.
In (3) we apply the coefficient of operator twice and we set the upper bound of the series to $infty$ without changing anything since we are adding zeros only.
In (4) we use the linearity of the coefficient of operator and we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.
In (5) we apply the substitution rule of the coefficient of operator with $z=frac{1}{1+u}$
begin{align*}
A(u)=sum_{m=0}^infty a_m u^m=sum_{m=0}^infty u^m [z^m]A(z)
end{align*}In (6) we do some simplifications.
In (7) we do some more simplifications and apply the same rule as we did in (4).
In (8) we select the coefficient of $u^{2k+1}$.
answered Jan 1 '18 at 19:25
Markus ScheuerMarkus Scheuer
61.3k456146
edited Jan 1 '18 at 20:02
answered Jan 1 '18 at 19:25
Markus ScheuerMarkus Scheuer
61.3k456146
answered Jan 1 '18 at 19:25
Markus ScheuerMarkus Scheuer
61.3k456146
answered Jan 1 '18 at 19:25
Markus ScheuerMarkus Scheuer
61.3k456146
61.3k456146
add a comment |
add a comment |
$begingroup$
More generally:
Theorem 1. For every nonnegative integers $x$, $y$ and $n$, we have
begin{equation}
dbinom{n+1}{x+y+1}=sum_{m=0}^{n}dbinom{m}{x}dbinom{n-m}{y}.
end{equation}
This equality rewrites as
begin{equation}
dbinom{n+1}{x+y+1} = sum_{m=x}^{n-y} dbinom{m}{x}dbinom{n-m}{y} ,
end{equation}
because all addends $dbinom{m}{x}dbinom{n-m}{y}$ are zero except for those where $x leq m leq n-y$.
Your identity is the particular case of the latter equality for $x = k$ and $y = k$.
Your nice bijective proof of the original identity can easily be generalized to a proof of Theorem 1; just count all ways of picking an $left(x+y+1right)$-element subset of $left{1,2,ldots,n+1right}$ according to the value of the $left(x+1right)$-th-lowest element of the subset. Indeed, for any given $m in left{0,1,ldots,nright}$, picking an $left(x+y+1right)$-element subset $S$ of $left{1,2,ldots,n+1right}$ whose $left(x+1right)$-th-lowest element is $m+1$ is tantamount to picking an $x$-element subset of $left{1,2,ldots,mright}$ (which will contain the $x$ elements of $S$ lower than $m+1$) and picking a $y$-element subset of $left{m+2,m+3,ldots,n+1right}$ (which will contain the $y$ elements of $S$ higher than $m+1$). This gives $dbinom{m}{x}dbinom{n-m}{y}$ for the number of choices.
As for other proofs:
An elementary proof is given in Proposition 3.32 (f) in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, Version of 10 January 2019. The proposition is obtained from Vandermonde convolution by several applications of upper negation.
Theorem 1 is also equivalent to the identity proven in Proof of $sum_{m=0}^{n}binom{m}{j}binom{n-m}{k-j}=binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity) (just set $j = x$ and $k = x+y$); the proof uses generating functions.
answered Jan 1 '18 at 12:21
darij grinbergdarij grinberg
10.8k33062
$endgroup$
add a comment |
$begingroup$
More generally:
Theorem 1. For every nonnegative integers $x$, $y$ and $n$, we have
begin{equation}
dbinom{n+1}{x+y+1}=sum_{m=0}^{n}dbinom{m}{x}dbinom{n-m}{y}.
end{equation}
This equality rewrites as
begin{equation}
dbinom{n+1}{x+y+1} = sum_{m=x}^{n-y} dbinom{m}{x}dbinom{n-m}{y} ,
end{equation}
because all addends $dbinom{m}{x}dbinom{n-m}{y}$ are zero except for those where $x leq m leq n-y$.
Your identity is the particular case of the latter equality for $x = k$ and $y = k$.
Your nice bijective proof of the original identity can easily be generalized to a proof of Theorem 1; just count all ways of picking an $left(x+y+1right)$-element subset of $left{1,2,ldots,n+1right}$ according to the value of the $left(x+1right)$-th-lowest element of the subset. Indeed, for any given $m in left{0,1,ldots,nright}$, picking an $left(x+y+1right)$-element subset $S$ of $left{1,2,ldots,n+1right}$ whose $left(x+1right)$-th-lowest element is $m+1$ is tantamount to picking an $x$-element subset of $left{1,2,ldots,mright}$ (which will contain the $x$ elements of $S$ lower than $m+1$) and picking a $y$-element subset of $left{m+2,m+3,ldots,n+1right}$ (which will contain the $y$ elements of $S$ higher than $m+1$). This gives $dbinom{m}{x}dbinom{n-m}{y}$ for the number of choices.
As for other proofs:
An elementary proof is given in Proposition 3.32 (f) in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, Version of 10 January 2019. The proposition is obtained from Vandermonde convolution by several applications of upper negation.
Theorem 1 is also equivalent to the identity proven in Proof of $sum_{m=0}^{n}binom{m}{j}binom{n-m}{k-j}=binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity) (just set $j = x$ and $k = x+y$); the proof uses generating functions.
answered Jan 1 '18 at 12:21
darij grinbergdarij grinberg
10.8k33062
$endgroup$
add a comment |
$begingroup$
More generally:
Theorem 1. For every nonnegative integers $x$, $y$ and $n$, we have
begin{equation}
dbinom{n+1}{x+y+1}=sum_{m=0}^{n}dbinom{m}{x}dbinom{n-m}{y}.
end{equation}
This equality rewrites as
begin{equation}
dbinom{n+1}{x+y+1} = sum_{m=x}^{n-y} dbinom{m}{x}dbinom{n-m}{y} ,
end{equation}
because all addends $dbinom{m}{x}dbinom{n-m}{y}$ are zero except for those where $x leq m leq n-y$.
Your identity is the particular case of the latter equality for $x = k$ and $y = k$.
Your nice bijective proof of the original identity can easily be generalized to a proof of Theorem 1; just count all ways of picking an $left(x+y+1right)$-element subset of $left{1,2,ldots,n+1right}$ according to the value of the $left(x+1right)$-th-lowest element of the subset. Indeed, for any given $m in left{0,1,ldots,nright}$, picking an $left(x+y+1right)$-element subset $S$ of $left{1,2,ldots,n+1right}$ whose $left(x+1right)$-th-lowest element is $m+1$ is tantamount to picking an $x$-element subset of $left{1,2,ldots,mright}$ (which will contain the $x$ elements of $S$ lower than $m+1$) and picking a $y$-element subset of $left{m+2,m+3,ldots,n+1right}$ (which will contain the $y$ elements of $S$ higher than $m+1$). This gives $dbinom{m}{x}dbinom{n-m}{y}$ for the number of choices.
As for other proofs:
An elementary proof is given in Proposition 3.32 (f) in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, Version of 10 January 2019. The proposition is obtained from Vandermonde convolution by several applications of upper negation.
Theorem 1 is also equivalent to the identity proven in Proof of $sum_{m=0}^{n}binom{m}{j}binom{n-m}{k-j}=binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity) (just set $j = x$ and $k = x+y$); the proof uses generating functions.
answered Jan 1 '18 at 12:21
darij grinbergdarij grinberg
10.8k33062
$endgroup$
More generally:
Theorem 1. For every nonnegative integers $x$, $y$ and $n$, we have
begin{equation}
dbinom{n+1}{x+y+1}=sum_{m=0}^{n}dbinom{m}{x}dbinom{n-m}{y}.
end{equation}
This equality rewrites as
begin{equation}
dbinom{n+1}{x+y+1} = sum_{m=x}^{n-y} dbinom{m}{x}dbinom{n-m}{y} ,
end{equation}
because all addends $dbinom{m}{x}dbinom{n-m}{y}$ are zero except for those where $x leq m leq n-y$.
Your identity is the particular case of the latter equality for $x = k$ and $y = k$.
Your nice bijective proof of the original identity can easily be generalized to a proof of Theorem 1; just count all ways of picking an $left(x+y+1right)$-element subset of $left{1,2,ldots,n+1right}$ according to the value of the $left(x+1right)$-th-lowest element of the subset. Indeed, for any given $m in left{0,1,ldots,nright}$, picking an $left(x+y+1right)$-element subset $S$ of $left{1,2,ldots,n+1right}$ whose $left(x+1right)$-th-lowest element is $m+1$ is tantamount to picking an $x$-element subset of $left{1,2,ldots,mright}$ (which will contain the $x$ elements of $S$ lower than $m+1$) and picking a $y$-element subset of $left{m+2,m+3,ldots,n+1right}$ (which will contain the $y$ elements of $S$ higher than $m+1$). This gives $dbinom{m}{x}dbinom{n-m}{y}$ for the number of choices.
As for other proofs:
An elementary proof is given in Proposition 3.32 (f) in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, Version of 10 January 2019. The proposition is obtained from Vandermonde convolution by several applications of upper negation.
Theorem 1 is also equivalent to the identity proven in Proof of $sum_{m=0}^{n}binom{m}{j}binom{n-m}{k-j}=binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity) (just set $j = x$ and $k = x+y$); the proof uses generating functions.
answered Jan 1 '18 at 12:21
darij grinbergdarij grinberg
10.8k33062
edited Jan 10 at 1:46
answered Jan 1 '18 at 12:21
darij grinbergdarij grinberg
10.8k33062
answered Jan 1 '18 at 12:21
darij grinbergdarij grinberg
10.8k33062
answered Jan 1 '18 at 12:21
darij grinbergdarij grinberg
10.8k33062
10.8k33062
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%2f2587436%2fis-there-an-algebraic-proof-for-sum-m-kn-k-binommk-binomn-mk%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$
Consider coefficient of $x^{n}$ in $[x^k(1-x)^{k+1}][x^k(1-x)^{k+1}]$.
$endgroup$
– Lord Shark the Unknown
Jan 1 '18 at 11:22