Proof for this binomial coefficient's equation
up vote
4
down vote
favorite
For $k, l in mathbb N$
$$sum_{i=0}^ksum_{j=0}^lbinom{i+j}i=binom{k+l+2}{k+1}-1$$
How can I prove this?
I thought some ideas with Pascal's triangle, counting paths on the grid and simple deformation of the formula.
It can be checked here (wolframalpha).
If the proof is difficult, please let me know the main idea.
Sorry for my poor English.
Thank you.
EDIT:
I got the great and short proof using Hockey-stick identity by Anubhab Ghosal, but because of this form, I could also get the Robert Z's specialized answer.
Then I don't think it is fully duplicate.
combinatorics summation binomial-coefficients
edited 14 hours ago
Martin Sleziak
44.6k7115269
asked 18 hours ago
るまし
235
New contributor
るまし is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
4
down vote
favorite
For $k, l in mathbb N$
$$sum_{i=0}^ksum_{j=0}^lbinom{i+j}i=binom{k+l+2}{k+1}-1$$
How can I prove this?
I thought some ideas with Pascal's triangle, counting paths on the grid and simple deformation of the formula.
It can be checked here (wolframalpha).
If the proof is difficult, please let me know the main idea.
Sorry for my poor English.
Thank you.
EDIT:
I got the great and short proof using Hockey-stick identity by Anubhab Ghosal, but because of this form, I could also get the Robert Z's specialized answer.
Then I don't think it is fully duplicate.
combinatorics summation binomial-coefficients
edited 14 hours ago
Martin Sleziak
44.6k7115269
asked 18 hours ago
るまし
235
New contributor
るまし is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
Possible duplicate of Prove $sumlimits_{i=0}^nbinom{i+k-1}{k-1}=binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)
– user10354138
17 hours ago
@user10354138 The double sum is related Hockey-Stick Identity but it is not a duplicate of the linked question. Moreover OP asks for a combinatorial proof (counting paths...)
– Robert Z
16 hours ago
@RobertZ The OP didn't ask for a combinatorial proof, only for a proof ("How can I prove this?" in the quote, not "How can I prove this combinatorially?"). It can be proved by applying the linked result twice, so it is a duplicate.
– user10354138
14 hours ago
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
12 hours ago
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
For $k, l in mathbb N$
$$sum_{i=0}^ksum_{j=0}^lbinom{i+j}i=binom{k+l+2}{k+1}-1$$
How can I prove this?
I thought some ideas with Pascal's triangle, counting paths on the grid and simple deformation of the formula.
It can be checked here (wolframalpha).
If the proof is difficult, please let me know the main idea.
Sorry for my poor English.
Thank you.
EDIT:
I got the great and short proof using Hockey-stick identity by Anubhab Ghosal, but because of this form, I could also get the Robert Z's specialized answer.
Then I don't think it is fully duplicate.
combinatorics summation binomial-coefficients
edited 14 hours ago
Martin Sleziak
44.6k7115269
asked 18 hours ago
るまし
235
New contributor
るまし is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
For $k, l in mathbb N$
$$sum_{i=0}^ksum_{j=0}^lbinom{i+j}i=binom{k+l+2}{k+1}-1$$
How can I prove this?
I thought some ideas with Pascal's triangle, counting paths on the grid and simple deformation of the formula.
It can be checked here (wolframalpha).
If the proof is difficult, please let me know the main idea.
Sorry for my poor English.
Thank you.
EDIT:
I got the great and short proof using Hockey-stick identity by Anubhab Ghosal, but because of this form, I could also get the Robert Z's specialized answer.
Then I don't think it is fully duplicate.
combinatorics summation binomial-coefficients
combinatorics summation binomial-coefficients
edited 14 hours ago
Martin Sleziak
44.6k7115269
asked 18 hours ago
るまし
235
New contributor
るまし is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 14 hours ago
Martin Sleziak
44.6k7115269
asked 18 hours ago
るまし
235
New contributor
るまし is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 14 hours ago
Martin Sleziak
44.6k7115269
edited 14 hours ago
Martin Sleziak
44.6k7115269
edited 14 hours ago
Martin Sleziak
44.6k7115269
44.6k7115269
asked 18 hours ago
るまし
235
New contributor
るまし is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 18 hours ago
るまし
235
asked 18 hours ago
るまし
235
235
New contributor
るまし is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
るまし is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
るまし is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
Possible duplicate of Prove $sumlimits_{i=0}^nbinom{i+k-1}{k-1}=binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)
– user10354138
17 hours ago
@user10354138 The double sum is related Hockey-Stick Identity but it is not a duplicate of the linked question. Moreover OP asks for a combinatorial proof (counting paths...)
– Robert Z
16 hours ago
@RobertZ The OP didn't ask for a combinatorial proof, only for a proof ("How can I prove this?" in the quote, not "How can I prove this combinatorially?"). It can be proved by applying the linked result twice, so it is a duplicate.
– user10354138
14 hours ago
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
12 hours ago
add a comment |
1
Possible duplicate of Prove $sumlimits_{i=0}^nbinom{i+k-1}{k-1}=binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)
– user10354138
17 hours ago
@user10354138 The double sum is related Hockey-Stick Identity but it is not a duplicate of the linked question. Moreover OP asks for a combinatorial proof (counting paths...)
– Robert Z
16 hours ago
@RobertZ The OP didn't ask for a combinatorial proof, only for a proof ("How can I prove this?" in the quote, not "How can I prove this combinatorially?"). It can be proved by applying the linked result twice, so it is a duplicate.
– user10354138
14 hours ago
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
12 hours ago
1
1
Possible duplicate of Prove $sumlimits_{i=0}^nbinom{i+k-1}{k-1}=binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)
– user10354138
17 hours ago
Possible duplicate of Prove $sumlimits_{i=0}^nbinom{i+k-1}{k-1}=binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)
– user10354138
17 hours ago
@user10354138 The double sum is related Hockey-Stick Identity but it is not a duplicate of the linked question. Moreover OP asks for a combinatorial proof (counting paths...)
– Robert Z
16 hours ago
@user10354138 The double sum is related Hockey-Stick Identity but it is not a duplicate of the linked question. Moreover OP asks for a combinatorial proof (counting paths...)
– Robert Z
16 hours ago
@RobertZ The OP didn't ask for a combinatorial proof, only for a proof ("How can I prove this?" in the quote, not "How can I prove this combinatorially?"). It can be proved by applying the linked result twice, so it is a duplicate.
– user10354138
14 hours ago
@RobertZ The OP didn't ask for a combinatorial proof, only for a proof ("How can I prove this?" in the quote, not "How can I prove this combinatorially?"). It can be proved by applying the linked result twice, so it is a duplicate.
– user10354138
14 hours ago
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
12 hours ago
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
12 hours ago
add a comment |
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binom{i+j}i$
counts the paths on the grid from $(0,0)$ to $(i,j)$ moving only right or up. So the double sum
$$sum_{i=0}^ksum_{j=0}^lbinom{i+j}i-1$$
counts the number of all such paths from $(0,0)$ to any vertex inside the rectangle $(0,k)times (0,l)$ different from $(0,0)$.
Now consider the paths from $(0,0)$ to $(k+1,l+1)$ different from $$(0,0)to (0,l+1)to (k+1,l+1)quadtext{and}quad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binom{k+l+2}{k+1}-2.$$
Now any path of the first kind can be completed to a path of the second kind by changing direction, going to the boundary of the rectangle
$(0,k+1)times(0,l+1)$ and then moving to the corner $(k+1,l+1)$ along the side.
Is this a bijection between the first set of paths and the second one?
answered 17 hours ago
Robert Z
91.9k1058129
add a comment |
up vote
5
down vote
$$displaystylesum_{i=0}^ksum_{j=0}^lbinom{i+j}i=sum_{i=0}^ksum_{j=i}^{i+l}binom{j}i=sum_{i=0}^kbinom{i+l+1}{i+1} ^{[1]}$$
$$=sum_{i=0}^kbinom{i+l+1}{l}=sum_{i=l}^{k+l+1}binom{i}{l}−1=binom{k+l+2}{k+1}-1 ^{[1]}$$
1. Hockey-Stick Identity
answered 17 hours ago
Anubhab Ghosal
73012
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',
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
});
}
});
るまし is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3036489%2fproof-for-this-binomial-coefficients-equation%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
up vote
3
down vote
accepted
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binom{i+j}i$
counts the paths on the grid from $(0,0)$ to $(i,j)$ moving only right or up. So the double sum
$$sum_{i=0}^ksum_{j=0}^lbinom{i+j}i-1$$
counts the number of all such paths from $(0,0)$ to any vertex inside the rectangle $(0,k)times (0,l)$ different from $(0,0)$.
Now consider the paths from $(0,0)$ to $(k+1,l+1)$ different from $$(0,0)to (0,l+1)to (k+1,l+1)quadtext{and}quad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binom{k+l+2}{k+1}-2.$$
Now any path of the first kind can be completed to a path of the second kind by changing direction, going to the boundary of the rectangle
$(0,k+1)times(0,l+1)$ and then moving to the corner $(k+1,l+1)$ along the side.
Is this a bijection between the first set of paths and the second one?
answered 17 hours ago
Robert Z
91.9k1058129
add a comment |
up vote
3
down vote
accepted
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binom{i+j}i$
counts the paths on the grid from $(0,0)$ to $(i,j)$ moving only right or up. So the double sum
$$sum_{i=0}^ksum_{j=0}^lbinom{i+j}i-1$$
counts the number of all such paths from $(0,0)$ to any vertex inside the rectangle $(0,k)times (0,l)$ different from $(0,0)$.
Now consider the paths from $(0,0)$ to $(k+1,l+1)$ different from $$(0,0)to (0,l+1)to (k+1,l+1)quadtext{and}quad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binom{k+l+2}{k+1}-2.$$
Now any path of the first kind can be completed to a path of the second kind by changing direction, going to the boundary of the rectangle
$(0,k+1)times(0,l+1)$ and then moving to the corner $(k+1,l+1)$ along the side.
Is this a bijection between the first set of paths and the second one?
answered 17 hours ago
Robert Z
91.9k1058129
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binom{i+j}i$
counts the paths on the grid from $(0,0)$ to $(i,j)$ moving only right or up. So the double sum
$$sum_{i=0}^ksum_{j=0}^lbinom{i+j}i-1$$
counts the number of all such paths from $(0,0)$ to any vertex inside the rectangle $(0,k)times (0,l)$ different from $(0,0)$.
Now consider the paths from $(0,0)$ to $(k+1,l+1)$ different from $$(0,0)to (0,l+1)to (k+1,l+1)quadtext{and}quad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binom{k+l+2}{k+1}-2.$$
Now any path of the first kind can be completed to a path of the second kind by changing direction, going to the boundary of the rectangle
$(0,k+1)times(0,l+1)$ and then moving to the corner $(k+1,l+1)$ along the side.
Is this a bijection between the first set of paths and the second one?
answered 17 hours ago
Robert Z
91.9k1058129
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binom{i+j}i$
counts the paths on the grid from $(0,0)$ to $(i,j)$ moving only right or up. So the double sum
$$sum_{i=0}^ksum_{j=0}^lbinom{i+j}i-1$$
counts the number of all such paths from $(0,0)$ to any vertex inside the rectangle $(0,k)times (0,l)$ different from $(0,0)$.
Now consider the paths from $(0,0)$ to $(k+1,l+1)$ different from $$(0,0)to (0,l+1)to (k+1,l+1)quadtext{and}quad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binom{k+l+2}{k+1}-2.$$
Now any path of the first kind can be completed to a path of the second kind by changing direction, going to the boundary of the rectangle
$(0,k+1)times(0,l+1)$ and then moving to the corner $(k+1,l+1)$ along the side.
Is this a bijection between the first set of paths and the second one?
answered 17 hours ago
Robert Z
91.9k1058129
edited 17 hours ago
answered 17 hours ago
Robert Z
91.9k1058129
answered 17 hours ago
Robert Z
91.9k1058129
answered 17 hours ago
Robert Z
91.9k1058129
91.9k1058129
add a comment |
add a comment |
up vote
5
down vote
$$displaystylesum_{i=0}^ksum_{j=0}^lbinom{i+j}i=sum_{i=0}^ksum_{j=i}^{i+l}binom{j}i=sum_{i=0}^kbinom{i+l+1}{i+1} ^{[1]}$$
$$=sum_{i=0}^kbinom{i+l+1}{l}=sum_{i=l}^{k+l+1}binom{i}{l}−1=binom{k+l+2}{k+1}-1 ^{[1]}$$
1. Hockey-Stick Identity
answered 17 hours ago
Anubhab Ghosal
73012
add a comment |
up vote
5
down vote
$$displaystylesum_{i=0}^ksum_{j=0}^lbinom{i+j}i=sum_{i=0}^ksum_{j=i}^{i+l}binom{j}i=sum_{i=0}^kbinom{i+l+1}{i+1} ^{[1]}$$
$$=sum_{i=0}^kbinom{i+l+1}{l}=sum_{i=l}^{k+l+1}binom{i}{l}−1=binom{k+l+2}{k+1}-1 ^{[1]}$$
1. Hockey-Stick Identity
answered 17 hours ago
Anubhab Ghosal
73012
add a comment |
up vote
5
down vote
up vote
5
down vote
$$displaystylesum_{i=0}^ksum_{j=0}^lbinom{i+j}i=sum_{i=0}^ksum_{j=i}^{i+l}binom{j}i=sum_{i=0}^kbinom{i+l+1}{i+1} ^{[1]}$$
$$=sum_{i=0}^kbinom{i+l+1}{l}=sum_{i=l}^{k+l+1}binom{i}{l}−1=binom{k+l+2}{k+1}-1 ^{[1]}$$
1. Hockey-Stick Identity
answered 17 hours ago
Anubhab Ghosal
73012
$$displaystylesum_{i=0}^ksum_{j=0}^lbinom{i+j}i=sum_{i=0}^ksum_{j=i}^{i+l}binom{j}i=sum_{i=0}^kbinom{i+l+1}{i+1} ^{[1]}$$
$$=sum_{i=0}^kbinom{i+l+1}{l}=sum_{i=l}^{k+l+1}binom{i}{l}−1=binom{k+l+2}{k+1}-1 ^{[1]}$$
1. Hockey-Stick Identity
answered 17 hours ago
Anubhab Ghosal
73012
edited 17 hours ago
answered 17 hours ago
Anubhab Ghosal
73012
answered 17 hours ago
Anubhab Ghosal
73012
answered 17 hours ago
Anubhab Ghosal
73012
73012
add a comment |
add a comment |
るまし is a new contributor. Be nice, and check out our Code of Conduct.
るまし is a new contributor. Be nice, and check out our Code of Conduct.
るまし is a new contributor. Be nice, and check out our Code of Conduct.
るまし is a new contributor. Be nice, and check out our Code of Conduct.
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3036489%2fproof-for-this-binomial-coefficients-equation%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
1
Possible duplicate of Prove $sumlimits_{i=0}^nbinom{i+k-1}{k-1}=binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)
– user10354138
17 hours ago
@user10354138 The double sum is related Hockey-Stick Identity but it is not a duplicate of the linked question. Moreover OP asks for a combinatorial proof (counting paths...)
– Robert Z
16 hours ago
@RobertZ The OP didn't ask for a combinatorial proof, only for a proof ("How can I prove this?" in the quote, not "How can I prove this combinatorially?"). It can be proved by applying the linked result twice, so it is a duplicate.
– user10354138
14 hours ago
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
12 hours ago