Proof for this binomial coefficient's equation
Clash Royale CLAN TAG#URR8PPP
For $k, l in mathbb N$
$$sum_i=0^ksum_j=0^lbinomi+ji=binomk+l+2k+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
add a comment |
For $k, l in mathbb N$
$$sum_i=0^ksum_j=0^lbinomi+ji=binomk+l+2k+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
1
Possible duplicate of Prove $sumlimits_i=0^nbinomi+k-1k-1=binomn+kk$ (a.k.a. Hockey-Stick Identity)
– user10354138
Dec 12 at 10:07
@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
Dec 12 at 11:30
@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
Dec 12 at 13:18
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
Dec 12 at 15:48
add a comment |
For $k, l in mathbb N$
$$sum_i=0^ksum_j=0^lbinomi+ji=binomk+l+2k+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
For $k, l in mathbb N$
$$sum_i=0^ksum_j=0^lbinomi+ji=binomk+l+2k+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 Dec 12 at 13:54
Martin Sleziak
44.6k7115270
44.6k7115270
asked Dec 12 at 9:58
るまし
235
235
1
Possible duplicate of Prove $sumlimits_i=0^nbinomi+k-1k-1=binomn+kk$ (a.k.a. Hockey-Stick Identity)
– user10354138
Dec 12 at 10:07
@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
Dec 12 at 11:30
@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
Dec 12 at 13:18
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
Dec 12 at 15:48
add a comment |
1
Possible duplicate of Prove $sumlimits_i=0^nbinomi+k-1k-1=binomn+kk$ (a.k.a. Hockey-Stick Identity)
– user10354138
Dec 12 at 10:07
@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
Dec 12 at 11:30
@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
Dec 12 at 13:18
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
Dec 12 at 15:48
1
1
Possible duplicate of Prove $sumlimits_i=0^nbinomi+k-1k-1=binomn+kk$ (a.k.a. Hockey-Stick Identity)
– user10354138
Dec 12 at 10:07
Possible duplicate of Prove $sumlimits_i=0^nbinomi+k-1k-1=binomn+kk$ (a.k.a. Hockey-Stick Identity)
– user10354138
Dec 12 at 10:07
@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
Dec 12 at 11:30
@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
Dec 12 at 11:30
@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
Dec 12 at 13:18
@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
Dec 12 at 13:18
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
Dec 12 at 15:48
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
Dec 12 at 15:48
add a comment |
3 Answers
3
active
oldest
votes
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binomi+ji$
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^lbinomi+ji-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)quadtextandquad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binomk+l+2k+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?
add a comment |
$$displaystylesum_i=0^ksum_j=0^lbinomi+ji=sum_i=0^ksum_j=i^i+lbinomji=sum_i=0^kbinomi+l+1i+1 ^[1]$$
$$=sum_i=0^kbinomi+l+1l=sum_i=l^k+l+1binomil−1=binomk+l+2k+1-1 ^[1]$$
1. Hockey-Stick Identity
add a comment |
$newcommandbbx[1],bbox[15px,border:1px groove navy]displaystyle#1,
newcommandbraces[1]leftlbrace,#1,rightrbrace
newcommandbracks[1]leftlbrack,#1,rightrbrack
newcommandddmathrmd
newcommandds[1]displaystyle#1
newcommandexpo[1],mathrme^#1,
newcommandicmathrmi
newcommandmc[1]mathcal#1
newcommandmrm[1]mathrm#1
newcommandpars[1]left(,#1,right)
newcommandpartiald[3]fracpartial^#1 #2partial #3^#1
newcommandroot[2],sqrt[#1],#2,,
newcommandtotald[3]fracmathrmd^#1 #2mathrmd #3^#1
newcommandverts[1]leftvert,#1,rightvert$
$dssum_i = 0^ksum_j = 0^ell
i + j choose i = k + ell + 2 choose k + 1 - 1: LARGE ?.qquad k, ell in mathbbN$.
beginalign
&bbox[10px,#ffd]sum_i = 0^ksum_j = 0^ell
i + j choose i =
sum_i = 0^ksum_j = 0^elli + j choose j =
sum_i = 0^ksum_j = 0^ell-i - 1 choose j
pars-1^,j
\[5mm] = &
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^, jpars1 + z^-i - 1 =
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^01 over z^, j,pars1 + z^-i - 1
\[5mm] = &
bracksz^0sum_i = 0^kpars1 over 1 + z^i + 1
sum_j = 0^ellpars-,1 over z^,j
\[5mm] = &
bracksz^0braces1 over 1 + z,
bracks1/pars1 + z^k + 1 - 1 over 1/pars1 + z - 1
bracespars-1/z^ell + 1 - 1 over -1/z - 1
\[5mm] = &
bracksz^0braces%
1 - pars1 + z^k + 1 over -z
,1 over pars1 + z^k + 1
bracespars-1^ell + 1 - z^ell + 1 over -1 - z,z over z^ell + 1
\[5mm] = &
bracksz^ell + 1braces1 - 1 over pars1 + z^k + 1
bracesz^ell + 1 + pars-1^ell over 1 + z
\[5mm] = &
pars-1^ellbracksz^ell + 1
brackspars1 + z^-1 - pars1 + z^-k - 2
\[5mm] = &
pars-1^ellbrackspars-1^ell + 1 - -k - 2 choose ell + 1
\[5mm] = &
-1 - pars-1^ell,-bracks-k - 2 + bracksell + 1 - 1 choose ell + 1pars-1^ell + 1
\[5mm] = &
-1 + k + ell + 2 choose ell + 1 =
bbxk + ell + 2 choose k + 1 - 1
endalign
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%2f3036489%2fproof-for-this-binomial-coefficients-equation%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
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binomi+ji$
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^lbinomi+ji-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)quadtextandquad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binomk+l+2k+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?
add a comment |
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binomi+ji$
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^lbinomi+ji-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)quadtextandquad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binomk+l+2k+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?
add a comment |
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binomi+ji$
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^lbinomi+ji-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)quadtextandquad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binomk+l+2k+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?
Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!
The binomial $binomi+ji$
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^lbinomi+ji-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)quadtextandquad
(0,0)to (k+1,0)to (k+1,l+1)$$ which are
$$binomk+l+2k+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?
edited Dec 12 at 10:42
answered Dec 12 at 10:31
Robert Z
92.9k1060131
92.9k1060131
add a comment |
add a comment |
$$displaystylesum_i=0^ksum_j=0^lbinomi+ji=sum_i=0^ksum_j=i^i+lbinomji=sum_i=0^kbinomi+l+1i+1 ^[1]$$
$$=sum_i=0^kbinomi+l+1l=sum_i=l^k+l+1binomil−1=binomk+l+2k+1-1 ^[1]$$
1. Hockey-Stick Identity
add a comment |
$$displaystylesum_i=0^ksum_j=0^lbinomi+ji=sum_i=0^ksum_j=i^i+lbinomji=sum_i=0^kbinomi+l+1i+1 ^[1]$$
$$=sum_i=0^kbinomi+l+1l=sum_i=l^k+l+1binomil−1=binomk+l+2k+1-1 ^[1]$$
1. Hockey-Stick Identity
add a comment |
$$displaystylesum_i=0^ksum_j=0^lbinomi+ji=sum_i=0^ksum_j=i^i+lbinomji=sum_i=0^kbinomi+l+1i+1 ^[1]$$
$$=sum_i=0^kbinomi+l+1l=sum_i=l^k+l+1binomil−1=binomk+l+2k+1-1 ^[1]$$
1. Hockey-Stick Identity
$$displaystylesum_i=0^ksum_j=0^lbinomi+ji=sum_i=0^ksum_j=i^i+lbinomji=sum_i=0^kbinomi+l+1i+1 ^[1]$$
$$=sum_i=0^kbinomi+l+1l=sum_i=l^k+l+1binomil−1=binomk+l+2k+1-1 ^[1]$$
1. Hockey-Stick Identity
edited Dec 12 at 10:17
answered Dec 12 at 10:12
Anubhab Ghosal
74212
74212
add a comment |
add a comment |
$newcommandbbx[1],bbox[15px,border:1px groove navy]displaystyle#1,
newcommandbraces[1]leftlbrace,#1,rightrbrace
newcommandbracks[1]leftlbrack,#1,rightrbrack
newcommandddmathrmd
newcommandds[1]displaystyle#1
newcommandexpo[1],mathrme^#1,
newcommandicmathrmi
newcommandmc[1]mathcal#1
newcommandmrm[1]mathrm#1
newcommandpars[1]left(,#1,right)
newcommandpartiald[3]fracpartial^#1 #2partial #3^#1
newcommandroot[2],sqrt[#1],#2,,
newcommandtotald[3]fracmathrmd^#1 #2mathrmd #3^#1
newcommandverts[1]leftvert,#1,rightvert$
$dssum_i = 0^ksum_j = 0^ell
i + j choose i = k + ell + 2 choose k + 1 - 1: LARGE ?.qquad k, ell in mathbbN$.
beginalign
&bbox[10px,#ffd]sum_i = 0^ksum_j = 0^ell
i + j choose i =
sum_i = 0^ksum_j = 0^elli + j choose j =
sum_i = 0^ksum_j = 0^ell-i - 1 choose j
pars-1^,j
\[5mm] = &
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^, jpars1 + z^-i - 1 =
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^01 over z^, j,pars1 + z^-i - 1
\[5mm] = &
bracksz^0sum_i = 0^kpars1 over 1 + z^i + 1
sum_j = 0^ellpars-,1 over z^,j
\[5mm] = &
bracksz^0braces1 over 1 + z,
bracks1/pars1 + z^k + 1 - 1 over 1/pars1 + z - 1
bracespars-1/z^ell + 1 - 1 over -1/z - 1
\[5mm] = &
bracksz^0braces%
1 - pars1 + z^k + 1 over -z
,1 over pars1 + z^k + 1
bracespars-1^ell + 1 - z^ell + 1 over -1 - z,z over z^ell + 1
\[5mm] = &
bracksz^ell + 1braces1 - 1 over pars1 + z^k + 1
bracesz^ell + 1 + pars-1^ell over 1 + z
\[5mm] = &
pars-1^ellbracksz^ell + 1
brackspars1 + z^-1 - pars1 + z^-k - 2
\[5mm] = &
pars-1^ellbrackspars-1^ell + 1 - -k - 2 choose ell + 1
\[5mm] = &
-1 - pars-1^ell,-bracks-k - 2 + bracksell + 1 - 1 choose ell + 1pars-1^ell + 1
\[5mm] = &
-1 + k + ell + 2 choose ell + 1 =
bbxk + ell + 2 choose k + 1 - 1
endalign
add a comment |
$newcommandbbx[1],bbox[15px,border:1px groove navy]displaystyle#1,
newcommandbraces[1]leftlbrace,#1,rightrbrace
newcommandbracks[1]leftlbrack,#1,rightrbrack
newcommandddmathrmd
newcommandds[1]displaystyle#1
newcommandexpo[1],mathrme^#1,
newcommandicmathrmi
newcommandmc[1]mathcal#1
newcommandmrm[1]mathrm#1
newcommandpars[1]left(,#1,right)
newcommandpartiald[3]fracpartial^#1 #2partial #3^#1
newcommandroot[2],sqrt[#1],#2,,
newcommandtotald[3]fracmathrmd^#1 #2mathrmd #3^#1
newcommandverts[1]leftvert,#1,rightvert$
$dssum_i = 0^ksum_j = 0^ell
i + j choose i = k + ell + 2 choose k + 1 - 1: LARGE ?.qquad k, ell in mathbbN$.
beginalign
&bbox[10px,#ffd]sum_i = 0^ksum_j = 0^ell
i + j choose i =
sum_i = 0^ksum_j = 0^elli + j choose j =
sum_i = 0^ksum_j = 0^ell-i - 1 choose j
pars-1^,j
\[5mm] = &
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^, jpars1 + z^-i - 1 =
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^01 over z^, j,pars1 + z^-i - 1
\[5mm] = &
bracksz^0sum_i = 0^kpars1 over 1 + z^i + 1
sum_j = 0^ellpars-,1 over z^,j
\[5mm] = &
bracksz^0braces1 over 1 + z,
bracks1/pars1 + z^k + 1 - 1 over 1/pars1 + z - 1
bracespars-1/z^ell + 1 - 1 over -1/z - 1
\[5mm] = &
bracksz^0braces%
1 - pars1 + z^k + 1 over -z
,1 over pars1 + z^k + 1
bracespars-1^ell + 1 - z^ell + 1 over -1 - z,z over z^ell + 1
\[5mm] = &
bracksz^ell + 1braces1 - 1 over pars1 + z^k + 1
bracesz^ell + 1 + pars-1^ell over 1 + z
\[5mm] = &
pars-1^ellbracksz^ell + 1
brackspars1 + z^-1 - pars1 + z^-k - 2
\[5mm] = &
pars-1^ellbrackspars-1^ell + 1 - -k - 2 choose ell + 1
\[5mm] = &
-1 - pars-1^ell,-bracks-k - 2 + bracksell + 1 - 1 choose ell + 1pars-1^ell + 1
\[5mm] = &
-1 + k + ell + 2 choose ell + 1 =
bbxk + ell + 2 choose k + 1 - 1
endalign
add a comment |
$newcommandbbx[1],bbox[15px,border:1px groove navy]displaystyle#1,
newcommandbraces[1]leftlbrace,#1,rightrbrace
newcommandbracks[1]leftlbrack,#1,rightrbrack
newcommandddmathrmd
newcommandds[1]displaystyle#1
newcommandexpo[1],mathrme^#1,
newcommandicmathrmi
newcommandmc[1]mathcal#1
newcommandmrm[1]mathrm#1
newcommandpars[1]left(,#1,right)
newcommandpartiald[3]fracpartial^#1 #2partial #3^#1
newcommandroot[2],sqrt[#1],#2,,
newcommandtotald[3]fracmathrmd^#1 #2mathrmd #3^#1
newcommandverts[1]leftvert,#1,rightvert$
$dssum_i = 0^ksum_j = 0^ell
i + j choose i = k + ell + 2 choose k + 1 - 1: LARGE ?.qquad k, ell in mathbbN$.
beginalign
&bbox[10px,#ffd]sum_i = 0^ksum_j = 0^ell
i + j choose i =
sum_i = 0^ksum_j = 0^elli + j choose j =
sum_i = 0^ksum_j = 0^ell-i - 1 choose j
pars-1^,j
\[5mm] = &
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^, jpars1 + z^-i - 1 =
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^01 over z^, j,pars1 + z^-i - 1
\[5mm] = &
bracksz^0sum_i = 0^kpars1 over 1 + z^i + 1
sum_j = 0^ellpars-,1 over z^,j
\[5mm] = &
bracksz^0braces1 over 1 + z,
bracks1/pars1 + z^k + 1 - 1 over 1/pars1 + z - 1
bracespars-1/z^ell + 1 - 1 over -1/z - 1
\[5mm] = &
bracksz^0braces%
1 - pars1 + z^k + 1 over -z
,1 over pars1 + z^k + 1
bracespars-1^ell + 1 - z^ell + 1 over -1 - z,z over z^ell + 1
\[5mm] = &
bracksz^ell + 1braces1 - 1 over pars1 + z^k + 1
bracesz^ell + 1 + pars-1^ell over 1 + z
\[5mm] = &
pars-1^ellbracksz^ell + 1
brackspars1 + z^-1 - pars1 + z^-k - 2
\[5mm] = &
pars-1^ellbrackspars-1^ell + 1 - -k - 2 choose ell + 1
\[5mm] = &
-1 - pars-1^ell,-bracks-k - 2 + bracksell + 1 - 1 choose ell + 1pars-1^ell + 1
\[5mm] = &
-1 + k + ell + 2 choose ell + 1 =
bbxk + ell + 2 choose k + 1 - 1
endalign
$newcommandbbx[1],bbox[15px,border:1px groove navy]displaystyle#1,
newcommandbraces[1]leftlbrace,#1,rightrbrace
newcommandbracks[1]leftlbrack,#1,rightrbrack
newcommandddmathrmd
newcommandds[1]displaystyle#1
newcommandexpo[1],mathrme^#1,
newcommandicmathrmi
newcommandmc[1]mathcal#1
newcommandmrm[1]mathrm#1
newcommandpars[1]left(,#1,right)
newcommandpartiald[3]fracpartial^#1 #2partial #3^#1
newcommandroot[2],sqrt[#1],#2,,
newcommandtotald[3]fracmathrmd^#1 #2mathrmd #3^#1
newcommandverts[1]leftvert,#1,rightvert$
$dssum_i = 0^ksum_j = 0^ell
i + j choose i = k + ell + 2 choose k + 1 - 1: LARGE ?.qquad k, ell in mathbbN$.
beginalign
&bbox[10px,#ffd]sum_i = 0^ksum_j = 0^ell
i + j choose i =
sum_i = 0^ksum_j = 0^elli + j choose j =
sum_i = 0^ksum_j = 0^ell-i - 1 choose j
pars-1^,j
\[5mm] = &
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^, jpars1 + z^-i - 1 =
sum_i = 0^ksum_j = 0^ellpars-1^,j
bracksz^01 over z^, j,pars1 + z^-i - 1
\[5mm] = &
bracksz^0sum_i = 0^kpars1 over 1 + z^i + 1
sum_j = 0^ellpars-,1 over z^,j
\[5mm] = &
bracksz^0braces1 over 1 + z,
bracks1/pars1 + z^k + 1 - 1 over 1/pars1 + z - 1
bracespars-1/z^ell + 1 - 1 over -1/z - 1
\[5mm] = &
bracksz^0braces%
1 - pars1 + z^k + 1 over -z
,1 over pars1 + z^k + 1
bracespars-1^ell + 1 - z^ell + 1 over -1 - z,z over z^ell + 1
\[5mm] = &
bracksz^ell + 1braces1 - 1 over pars1 + z^k + 1
bracesz^ell + 1 + pars-1^ell over 1 + z
\[5mm] = &
pars-1^ellbracksz^ell + 1
brackspars1 + z^-1 - pars1 + z^-k - 2
\[5mm] = &
pars-1^ellbrackspars-1^ell + 1 - -k - 2 choose ell + 1
\[5mm] = &
-1 - pars-1^ell,-bracks-k - 2 + bracksell + 1 - 1 choose ell + 1pars-1^ell + 1
\[5mm] = &
-1 + k + ell + 2 choose ell + 1 =
bbxk + ell + 2 choose k + 1 - 1
endalign
answered 2 days ago
Felix Marin
66.9k7107139
66.9k7107139
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.
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^nbinomi+k-1k-1=binomn+kk$ (a.k.a. Hockey-Stick Identity)
– user10354138
Dec 12 at 10:07
@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
Dec 12 at 11:30
@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
Dec 12 at 13:18
@user10354138 Fine. So we have a different opinion on this matter. Have a nice day.
– Robert Z
Dec 12 at 15:48