A simple finite combinatorial sum I found, that seems to work, would have good reasons to work, but I can't...












23














I was doing a consistency check for some calculations I'm performing for my master thesis (roughly - about a problem in discrete bayesian model selection) - and it turns out that my choice of priors is only consistent if this identity is true:



$$sum_{k=0}^{N}left[ binom{k+j}{j}binom{N-k+j}{j}right] = binom{N+2j+1}{2j+1}$$



Now, this seems to work for small numbers, but I searched for it a lot in the literature and I can't find it.(I have a physics background so probably my knowledge of proper "literature" is the problem here). Neither I can demonstrate it!
Has anyone of you seen this before? Can this be rewritten equivalently in some more commonly seen way? Can it be proven right...or wrong?
Thanks in advance! :)






combinatorics summation binomial-coefficients







share|cite|improve this question




















  • 2




    For an interpretable explanation of why this identity holds, see math.stackexchange.com/questions/2327556/…
    – David Foley
    Dec 6 at 16:07








  • 4




    Just as a remark, any time I've ever needed to find a combinatorial identity, I've looked in Henry Gould's Table of Combinatorial Identities ( available on math.wvu.edu/~gould) and without fail I've either found it or found something that allowed me to prove what I needed. Yours looks like it's doable with what's in Vol 4 Sec 1.10
    – user113102
    Dec 6 at 17:32












  • @user113102 The index of summation doesn't appear in the right position for 1.10, though.
    – chepner
    Dec 6 at 20:32










  • Taking $alpha$, $r$ = $j$ and using standard binomial formulas e.g. ${n choose i} = {n choose n-i}$ and you're good, no? I admittedly didn't look too hard.
    – user113102
    Dec 6 at 21:27












  • I have a copy of GouldBK.pdf that has, with some symbol definitions, this identity in equation 3.2. My copy is from years ago but I can't find a version on the internet, presently. But the original source says it might come back up? Incidently the Riordan Transform section 1.4 has a (more or less) generic formula for doing this type of identity. I don't know if I can legally post a copy of the paper somewhere for access (it's quite good). Can copyright laws be retroactive?
    – rrogers
    Dec 11 at 20:56


















23














I was doing a consistency check for some calculations I'm performing for my master thesis (roughly - about a problem in discrete bayesian model selection) - and it turns out that my choice of priors is only consistent if this identity is true:



$$sum_{k=0}^{N}left[ binom{k+j}{j}binom{N-k+j}{j}right] = binom{N+2j+1}{2j+1}$$



Now, this seems to work for small numbers, but I searched for it a lot in the literature and I can't find it.(I have a physics background so probably my knowledge of proper "literature" is the problem here). Neither I can demonstrate it!
Has anyone of you seen this before? Can this be rewritten equivalently in some more commonly seen way? Can it be proven right...or wrong?
Thanks in advance! :)






combinatorics summation binomial-coefficients







share|cite|improve this question




















  • 2




    For an interpretable explanation of why this identity holds, see math.stackexchange.com/questions/2327556/…
    – David Foley
    Dec 6 at 16:07








  • 4




    Just as a remark, any time I've ever needed to find a combinatorial identity, I've looked in Henry Gould's Table of Combinatorial Identities ( available on math.wvu.edu/~gould) and without fail I've either found it or found something that allowed me to prove what I needed. Yours looks like it's doable with what's in Vol 4 Sec 1.10
    – user113102
    Dec 6 at 17:32












  • @user113102 The index of summation doesn't appear in the right position for 1.10, though.
    – chepner
    Dec 6 at 20:32










  • Taking $alpha$, $r$ = $j$ and using standard binomial formulas e.g. ${n choose i} = {n choose n-i}$ and you're good, no? I admittedly didn't look too hard.
    – user113102
    Dec 6 at 21:27












  • I have a copy of GouldBK.pdf that has, with some symbol definitions, this identity in equation 3.2. My copy is from years ago but I can't find a version on the internet, presently. But the original source says it might come back up? Incidently the Riordan Transform section 1.4 has a (more or less) generic formula for doing this type of identity. I don't know if I can legally post a copy of the paper somewhere for access (it's quite good). Can copyright laws be retroactive?
    – rrogers
    Dec 11 at 20:56
















23












23








23


6





I was doing a consistency check for some calculations I'm performing for my master thesis (roughly - about a problem in discrete bayesian model selection) - and it turns out that my choice of priors is only consistent if this identity is true:



$$sum_{k=0}^{N}left[ binom{k+j}{j}binom{N-k+j}{j}right] = binom{N+2j+1}{2j+1}$$



Now, this seems to work for small numbers, but I searched for it a lot in the literature and I can't find it.(I have a physics background so probably my knowledge of proper "literature" is the problem here). Neither I can demonstrate it!
Has anyone of you seen this before? Can this be rewritten equivalently in some more commonly seen way? Can it be proven right...or wrong?
Thanks in advance! :)






combinatorics summation binomial-coefficients







share|cite|improve this question















I was doing a consistency check for some calculations I'm performing for my master thesis (roughly - about a problem in discrete bayesian model selection) - and it turns out that my choice of priors is only consistent if this identity is true:



$$sum_{k=0}^{N}left[ binom{k+j}{j}binom{N-k+j}{j}right] = binom{N+2j+1}{2j+1}$$



Now, this seems to work for small numbers, but I searched for it a lot in the literature and I can't find it.(I have a physics background so probably my knowledge of proper "literature" is the problem here). Neither I can demonstrate it!
Has anyone of you seen this before? Can this be rewritten equivalently in some more commonly seen way? Can it be proven right...or wrong?
Thanks in advance! :)






combinatorics summation binomial-coefficients




combinatorics summation binomial-coefficients






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 6 at 12:53









N. F. Taussig

43.5k93355




43.5k93355










asked Dec 6 at 10:59









Rocco

1247




1247








  • 2




    For an interpretable explanation of why this identity holds, see math.stackexchange.com/questions/2327556/…
    – David Foley
    Dec 6 at 16:07








  • 4




    Just as a remark, any time I've ever needed to find a combinatorial identity, I've looked in Henry Gould's Table of Combinatorial Identities ( available on math.wvu.edu/~gould) and without fail I've either found it or found something that allowed me to prove what I needed. Yours looks like it's doable with what's in Vol 4 Sec 1.10
    – user113102
    Dec 6 at 17:32












  • @user113102 The index of summation doesn't appear in the right position for 1.10, though.
    – chepner
    Dec 6 at 20:32










  • Taking $alpha$, $r$ = $j$ and using standard binomial formulas e.g. ${n choose i} = {n choose n-i}$ and you're good, no? I admittedly didn't look too hard.
    – user113102
    Dec 6 at 21:27












  • I have a copy of GouldBK.pdf that has, with some symbol definitions, this identity in equation 3.2. My copy is from years ago but I can't find a version on the internet, presently. But the original source says it might come back up? Incidently the Riordan Transform section 1.4 has a (more or less) generic formula for doing this type of identity. I don't know if I can legally post a copy of the paper somewhere for access (it's quite good). Can copyright laws be retroactive?
    – rrogers
    Dec 11 at 20:56
















  • 2




    For an interpretable explanation of why this identity holds, see math.stackexchange.com/questions/2327556/…
    – David Foley
    Dec 6 at 16:07








  • 4




    Just as a remark, any time I've ever needed to find a combinatorial identity, I've looked in Henry Gould's Table of Combinatorial Identities ( available on math.wvu.edu/~gould) and without fail I've either found it or found something that allowed me to prove what I needed. Yours looks like it's doable with what's in Vol 4 Sec 1.10
    – user113102
    Dec 6 at 17:32












  • @user113102 The index of summation doesn't appear in the right position for 1.10, though.
    – chepner
    Dec 6 at 20:32










  • Taking $alpha$, $r$ = $j$ and using standard binomial formulas e.g. ${n choose i} = {n choose n-i}$ and you're good, no? I admittedly didn't look too hard.
    – user113102
    Dec 6 at 21:27












  • I have a copy of GouldBK.pdf that has, with some symbol definitions, this identity in equation 3.2. My copy is from years ago but I can't find a version on the internet, presently. But the original source says it might come back up? Incidently the Riordan Transform section 1.4 has a (more or less) generic formula for doing this type of identity. I don't know if I can legally post a copy of the paper somewhere for access (it's quite good). Can copyright laws be retroactive?
    – rrogers
    Dec 11 at 20:56










2




2




For an interpretable explanation of why this identity holds, see math.stackexchange.com/questions/2327556/…
– David Foley
Dec 6 at 16:07






For an interpretable explanation of why this identity holds, see math.stackexchange.com/questions/2327556/…
– David Foley
Dec 6 at 16:07






4




4




Just as a remark, any time I've ever needed to find a combinatorial identity, I've looked in Henry Gould's Table of Combinatorial Identities ( available on math.wvu.edu/~gould) and without fail I've either found it or found something that allowed me to prove what I needed. Yours looks like it's doable with what's in Vol 4 Sec 1.10
– user113102
Dec 6 at 17:32






Just as a remark, any time I've ever needed to find a combinatorial identity, I've looked in Henry Gould's Table of Combinatorial Identities ( available on math.wvu.edu/~gould) and without fail I've either found it or found something that allowed me to prove what I needed. Yours looks like it's doable with what's in Vol 4 Sec 1.10
– user113102
Dec 6 at 17:32














@user113102 The index of summation doesn't appear in the right position for 1.10, though.
– chepner
Dec 6 at 20:32




@user113102 The index of summation doesn't appear in the right position for 1.10, though.
– chepner
Dec 6 at 20:32












Taking $alpha$, $r$ = $j$ and using standard binomial formulas e.g. ${n choose i} = {n choose n-i}$ and you're good, no? I admittedly didn't look too hard.
– user113102
Dec 6 at 21:27






Taking $alpha$, $r$ = $j$ and using standard binomial formulas e.g. ${n choose i} = {n choose n-i}$ and you're good, no? I admittedly didn't look too hard.
– user113102
Dec 6 at 21:27














I have a copy of GouldBK.pdf that has, with some symbol definitions, this identity in equation 3.2. My copy is from years ago but I can't find a version on the internet, presently. But the original source says it might come back up? Incidently the Riordan Transform section 1.4 has a (more or less) generic formula for doing this type of identity. I don't know if I can legally post a copy of the paper somewhere for access (it's quite good). Can copyright laws be retroactive?
– rrogers
Dec 11 at 20:56






I have a copy of GouldBK.pdf that has, with some symbol definitions, this identity in equation 3.2. My copy is from years ago but I can't find a version on the internet, presently. But the original source says it might come back up? Incidently the Riordan Transform section 1.4 has a (more or less) generic formula for doing this type of identity. I don't know if I can legally post a copy of the paper somewhere for access (it's quite good). Can copyright laws be retroactive?
– rrogers
Dec 11 at 20:56












2 Answers
2






active

oldest

votes


















42














Your identity is correct. I don't know a reference offhand, but here is a proof.



The right side, $binom{N+2j+1}{2j+1}$, is the number of bitstrings of length $N+2j+1$ consisting of $N$ zeroes and $2j+1$ ones.



The sum on the left counts the same set of bitstrings. Namely, for $0le kle N$, the term $binom{k+j}jbinom{N-k+j}j$ is the number of those bitstrings in which the middle one, with $j$ ones on either side, is in the $k+j+1^text{st}$ position; i.e., it has $k$ zeroes and $j$ ones to the left, $N-k$ zeroes and $j$ ones to the right.




P.S. I found your identity in László Lovász, Combinatorial Problems and Exercises, North-Holland, 1979 (the first edition), where it is Exercise 1.42(i) on p. 18, with hint on p. 96 and solution on p. 172. Lovász gives the identity in the following (more general) form:
$$sum_{k=0}^mbinom{u+k}kbinom{v-k}{m-k}=binom{u+v+1}m.$$
If we set $m=N$, $u=j$, $v=N+j$, this becomes
$$sum_{k=0}^Nbinom{j+k}kbinom{N+j-k}{N-k}=binom{N+2j+1}N$$
which is plainly equivalent to your identity
$$sum_{k=0}^Nbinom{k+j}jbinom{N-k+j}j=binom{N+2j+1}{2j+1}.$$






share|cite|improve this answer































    8














    We have



    $$sum_{k=0}^N {k+jchoose j} {N-k+jchoose j}
    = sum_{k=0}^N {k+jchoose j} {N-k+jchoose N-k}
    \ = sum_{k=0}^N {k+jchoose j} [z^{N-k}] (1+z)^{N-k+j}
    = [z^N] (1+z)^{N+j} sum_{k=0}^N {k+jchoose j} z^k (1+z)^{-k}.$$



    Now we may extend $k$ beyond $N$ as there is no contribution to
    $[z^N]$ at the front in this case (we have $z^k (1+z)^{-k} = z^k
    +cdots$    )



    $$[z^N] (1+z)^{N+j} sum_{kge 0} {k+jchoose j} z^k (1+z)^{-k}
    = [z^N] (1+z)^{N+j} frac{1}{(1-z/(1+z))^{j+1}}
    \ = [z^N] (1+z)^{N+j} frac{(1+z)^{j+1}}{(1+z-z)^{j+1}}
    = [z^N] (1+z)^{N+2j+1} = {N+2j+1choose 2j+1}.$$






    share|cite|improve this answer























    • I'm sorry, I'm not familiar with these kind of manipulations and/or notation. What's the definition of the object $[z^n]$? I mean, even though it's sort of self explanatory from what you did...it's an interesting notation that, with my tiny experience, I have never seen. Do you have any reference I can read to get a grasp on it? Thanks!
      – Rocco
      Dec 7 at 9:26








    • 2




      There is this at Wikipedia on formal power series.
      – Marko Riedel
      Dec 7 at 13:19











    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
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3028345%2fa-simple-finite-combinatorial-sum-i-found-that-seems-to-work-would-have-good-r%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









    42














    Your identity is correct. I don't know a reference offhand, but here is a proof.



    The right side, $binom{N+2j+1}{2j+1}$, is the number of bitstrings of length $N+2j+1$ consisting of $N$ zeroes and $2j+1$ ones.



    The sum on the left counts the same set of bitstrings. Namely, for $0le kle N$, the term $binom{k+j}jbinom{N-k+j}j$ is the number of those bitstrings in which the middle one, with $j$ ones on either side, is in the $k+j+1^text{st}$ position; i.e., it has $k$ zeroes and $j$ ones to the left, $N-k$ zeroes and $j$ ones to the right.




    P.S. I found your identity in László Lovász, Combinatorial Problems and Exercises, North-Holland, 1979 (the first edition), where it is Exercise 1.42(i) on p. 18, with hint on p. 96 and solution on p. 172. Lovász gives the identity in the following (more general) form:
    $$sum_{k=0}^mbinom{u+k}kbinom{v-k}{m-k}=binom{u+v+1}m.$$
    If we set $m=N$, $u=j$, $v=N+j$, this becomes
    $$sum_{k=0}^Nbinom{j+k}kbinom{N+j-k}{N-k}=binom{N+2j+1}N$$
    which is plainly equivalent to your identity
    $$sum_{k=0}^Nbinom{k+j}jbinom{N-k+j}j=binom{N+2j+1}{2j+1}.$$






    share|cite|improve this answer




























      42














      Your identity is correct. I don't know a reference offhand, but here is a proof.



      The right side, $binom{N+2j+1}{2j+1}$, is the number of bitstrings of length $N+2j+1$ consisting of $N$ zeroes and $2j+1$ ones.



      The sum on the left counts the same set of bitstrings. Namely, for $0le kle N$, the term $binom{k+j}jbinom{N-k+j}j$ is the number of those bitstrings in which the middle one, with $j$ ones on either side, is in the $k+j+1^text{st}$ position; i.e., it has $k$ zeroes and $j$ ones to the left, $N-k$ zeroes and $j$ ones to the right.




      P.S. I found your identity in László Lovász, Combinatorial Problems and Exercises, North-Holland, 1979 (the first edition), where it is Exercise 1.42(i) on p. 18, with hint on p. 96 and solution on p. 172. Lovász gives the identity in the following (more general) form:
      $$sum_{k=0}^mbinom{u+k}kbinom{v-k}{m-k}=binom{u+v+1}m.$$
      If we set $m=N$, $u=j$, $v=N+j$, this becomes
      $$sum_{k=0}^Nbinom{j+k}kbinom{N+j-k}{N-k}=binom{N+2j+1}N$$
      which is plainly equivalent to your identity
      $$sum_{k=0}^Nbinom{k+j}jbinom{N-k+j}j=binom{N+2j+1}{2j+1}.$$






      share|cite|improve this answer


























        42












        42








        42






        Your identity is correct. I don't know a reference offhand, but here is a proof.



        The right side, $binom{N+2j+1}{2j+1}$, is the number of bitstrings of length $N+2j+1$ consisting of $N$ zeroes and $2j+1$ ones.



        The sum on the left counts the same set of bitstrings. Namely, for $0le kle N$, the term $binom{k+j}jbinom{N-k+j}j$ is the number of those bitstrings in which the middle one, with $j$ ones on either side, is in the $k+j+1^text{st}$ position; i.e., it has $k$ zeroes and $j$ ones to the left, $N-k$ zeroes and $j$ ones to the right.




        P.S. I found your identity in László Lovász, Combinatorial Problems and Exercises, North-Holland, 1979 (the first edition), where it is Exercise 1.42(i) on p. 18, with hint on p. 96 and solution on p. 172. Lovász gives the identity in the following (more general) form:
        $$sum_{k=0}^mbinom{u+k}kbinom{v-k}{m-k}=binom{u+v+1}m.$$
        If we set $m=N$, $u=j$, $v=N+j$, this becomes
        $$sum_{k=0}^Nbinom{j+k}kbinom{N+j-k}{N-k}=binom{N+2j+1}N$$
        which is plainly equivalent to your identity
        $$sum_{k=0}^Nbinom{k+j}jbinom{N-k+j}j=binom{N+2j+1}{2j+1}.$$






        share|cite|improve this answer














        Your identity is correct. I don't know a reference offhand, but here is a proof.



        The right side, $binom{N+2j+1}{2j+1}$, is the number of bitstrings of length $N+2j+1$ consisting of $N$ zeroes and $2j+1$ ones.



        The sum on the left counts the same set of bitstrings. Namely, for $0le kle N$, the term $binom{k+j}jbinom{N-k+j}j$ is the number of those bitstrings in which the middle one, with $j$ ones on either side, is in the $k+j+1^text{st}$ position; i.e., it has $k$ zeroes and $j$ ones to the left, $N-k$ zeroes and $j$ ones to the right.




        P.S. I found your identity in László Lovász, Combinatorial Problems and Exercises, North-Holland, 1979 (the first edition), where it is Exercise 1.42(i) on p. 18, with hint on p. 96 and solution on p. 172. Lovász gives the identity in the following (more general) form:
        $$sum_{k=0}^mbinom{u+k}kbinom{v-k}{m-k}=binom{u+v+1}m.$$
        If we set $m=N$, $u=j$, $v=N+j$, this becomes
        $$sum_{k=0}^Nbinom{j+k}kbinom{N+j-k}{N-k}=binom{N+2j+1}N$$
        which is plainly equivalent to your identity
        $$sum_{k=0}^Nbinom{k+j}jbinom{N-k+j}j=binom{N+2j+1}{2j+1}.$$







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Dec 6 at 12:43

























        answered Dec 6 at 11:31









        bof

        50.1k457119




        50.1k457119























            8














            We have



            $$sum_{k=0}^N {k+jchoose j} {N-k+jchoose j}
            = sum_{k=0}^N {k+jchoose j} {N-k+jchoose N-k}
            \ = sum_{k=0}^N {k+jchoose j} [z^{N-k}] (1+z)^{N-k+j}
            = [z^N] (1+z)^{N+j} sum_{k=0}^N {k+jchoose j} z^k (1+z)^{-k}.$$



            Now we may extend $k$ beyond $N$ as there is no contribution to
            $[z^N]$ at the front in this case (we have $z^k (1+z)^{-k} = z^k
            +cdots$            )



            $$[z^N] (1+z)^{N+j} sum_{kge 0} {k+jchoose j} z^k (1+z)^{-k}
            = [z^N] (1+z)^{N+j} frac{1}{(1-z/(1+z))^{j+1}}
            \ = [z^N] (1+z)^{N+j} frac{(1+z)^{j+1}}{(1+z-z)^{j+1}}
            = [z^N] (1+z)^{N+2j+1} = {N+2j+1choose 2j+1}.$$






            share|cite|improve this answer























            • I'm sorry, I'm not familiar with these kind of manipulations and/or notation. What's the definition of the object $[z^n]$? I mean, even though it's sort of self explanatory from what you did...it's an interesting notation that, with my tiny experience, I have never seen. Do you have any reference I can read to get a grasp on it? Thanks!
              – Rocco
              Dec 7 at 9:26








            • 2




              There is this at Wikipedia on formal power series.
              – Marko Riedel
              Dec 7 at 13:19
















            8














            We have



            $$sum_{k=0}^N {k+jchoose j} {N-k+jchoose j}
            = sum_{k=0}^N {k+jchoose j} {N-k+jchoose N-k}
            \ = sum_{k=0}^N {k+jchoose j} [z^{N-k}] (1+z)^{N-k+j}
            = [z^N] (1+z)^{N+j} sum_{k=0}^N {k+jchoose j} z^k (1+z)^{-k}.$$



            Now we may extend $k$ beyond $N$ as there is no contribution to
            $[z^N]$ at the front in this case (we have $z^k (1+z)^{-k} = z^k
            +cdots$            )



            $$[z^N] (1+z)^{N+j} sum_{kge 0} {k+jchoose j} z^k (1+z)^{-k}
            = [z^N] (1+z)^{N+j} frac{1}{(1-z/(1+z))^{j+1}}
            \ = [z^N] (1+z)^{N+j} frac{(1+z)^{j+1}}{(1+z-z)^{j+1}}
            = [z^N] (1+z)^{N+2j+1} = {N+2j+1choose 2j+1}.$$






            share|cite|improve this answer























            • I'm sorry, I'm not familiar with these kind of manipulations and/or notation. What's the definition of the object $[z^n]$? I mean, even though it's sort of self explanatory from what you did...it's an interesting notation that, with my tiny experience, I have never seen. Do you have any reference I can read to get a grasp on it? Thanks!
              – Rocco
              Dec 7 at 9:26








            • 2




              There is this at Wikipedia on formal power series.
              – Marko Riedel
              Dec 7 at 13:19














            8












            8








            8






            We have



            $$sum_{k=0}^N {k+jchoose j} {N-k+jchoose j}
            = sum_{k=0}^N {k+jchoose j} {N-k+jchoose N-k}
            \ = sum_{k=0}^N {k+jchoose j} [z^{N-k}] (1+z)^{N-k+j}
            = [z^N] (1+z)^{N+j} sum_{k=0}^N {k+jchoose j} z^k (1+z)^{-k}.$$



            Now we may extend $k$ beyond $N$ as there is no contribution to
            $[z^N]$ at the front in this case (we have $z^k (1+z)^{-k} = z^k
            +cdots$            )



            $$[z^N] (1+z)^{N+j} sum_{kge 0} {k+jchoose j} z^k (1+z)^{-k}
            = [z^N] (1+z)^{N+j} frac{1}{(1-z/(1+z))^{j+1}}
            \ = [z^N] (1+z)^{N+j} frac{(1+z)^{j+1}}{(1+z-z)^{j+1}}
            = [z^N] (1+z)^{N+2j+1} = {N+2j+1choose 2j+1}.$$






            share|cite|improve this answer














            We have



            $$sum_{k=0}^N {k+jchoose j} {N-k+jchoose j}
            = sum_{k=0}^N {k+jchoose j} {N-k+jchoose N-k}
            \ = sum_{k=0}^N {k+jchoose j} [z^{N-k}] (1+z)^{N-k+j}
            = [z^N] (1+z)^{N+j} sum_{k=0}^N {k+jchoose j} z^k (1+z)^{-k}.$$



            Now we may extend $k$ beyond $N$ as there is no contribution to
            $[z^N]$ at the front in this case (we have $z^k (1+z)^{-k} = z^k
            +cdots$            )



            $$[z^N] (1+z)^{N+j} sum_{kge 0} {k+jchoose j} z^k (1+z)^{-k}
            = [z^N] (1+z)^{N+j} frac{1}{(1-z/(1+z))^{j+1}}
            \ = [z^N] (1+z)^{N+j} frac{(1+z)^{j+1}}{(1+z-z)^{j+1}}
            = [z^N] (1+z)^{N+2j+1} = {N+2j+1choose 2j+1}.$$







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Dec 6 at 17:13

























            answered Dec 6 at 14:10









            Marko Riedel

            38.9k339107




            38.9k339107












            • I'm sorry, I'm not familiar with these kind of manipulations and/or notation. What's the definition of the object $[z^n]$? I mean, even though it's sort of self explanatory from what you did...it's an interesting notation that, with my tiny experience, I have never seen. Do you have any reference I can read to get a grasp on it? Thanks!
              – Rocco
              Dec 7 at 9:26








            • 2




              There is this at Wikipedia on formal power series.
              – Marko Riedel
              Dec 7 at 13:19


















            • I'm sorry, I'm not familiar with these kind of manipulations and/or notation. What's the definition of the object $[z^n]$? I mean, even though it's sort of self explanatory from what you did...it's an interesting notation that, with my tiny experience, I have never seen. Do you have any reference I can read to get a grasp on it? Thanks!
              – Rocco
              Dec 7 at 9:26








            • 2




              There is this at Wikipedia on formal power series.
              – Marko Riedel
              Dec 7 at 13:19
















            I'm sorry, I'm not familiar with these kind of manipulations and/or notation. What's the definition of the object $[z^n]$? I mean, even though it's sort of self explanatory from what you did...it's an interesting notation that, with my tiny experience, I have never seen. Do you have any reference I can read to get a grasp on it? Thanks!
            – Rocco
            Dec 7 at 9:26






            I'm sorry, I'm not familiar with these kind of manipulations and/or notation. What's the definition of the object $[z^n]$? I mean, even though it's sort of self explanatory from what you did...it's an interesting notation that, with my tiny experience, I have never seen. Do you have any reference I can read to get a grasp on it? Thanks!
            – Rocco
            Dec 7 at 9:26






            2




            2




            There is this at Wikipedia on formal power series.
            – Marko Riedel
            Dec 7 at 13:19




            There is this at Wikipedia on formal power series.
            – Marko Riedel
            Dec 7 at 13:19


















            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3028345%2fa-simple-finite-combinatorial-sum-i-found-that-seems-to-work-would-have-good-r%23new-answer', 'question_page');
            }
            );

            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







            -

            Popular posts from this blog

            Plaza Victoria

            Image
            Plaza Victoria Plaza Victoria en 2017 Otros nombres Plaza de La Victoria Localización El Almendral, Valparaíso, Chile Vías adyacentes Chacabuco, Molina, Plaza Victoria y Edwards Creación 1841 Metro Bellavista Ubicación 33°02′46″S 71°37′11″O  /  -33.04624167, -71.61980833 Coordenadas: 33°02′46″S 71°37′11″O  /  -33.04624167, -71.61980833 [editar datos en Wikidata] La Plaza Victoria , también llamada Plaza de la Victoria , [ 1 ] ​ es una plaza ubicada en el sector El Almendral del plan de la ciudad de Valparaíso, Chile, de importancia patrimonial, que incluye valiosas estatuas y especies vegetales. [ 2 ] ​ La plaza se creó como tal en la primera mitad del siglo XIX, tomando previamente los nombres de Plaza Nueva y Plaza de Orrego . Si bien desde sus inicios tuvo relevancia histórica, no fue sino a partir de fines de los años 1860 cuando comenzó a cobrar mayor importancia y se convirtió en uno de los principales centros sociales de l...
            Read more

            Puebla de Zaragoza

            Image
            Para otros usos de este término, véase Puebla (desambiguación). Heroica Puebla de Zaragoza Localidad De arriba a abajo de izquierda a derecha: Estrella de Puebla, Volcán Popocatépetl, Catedral de Puebla, Monumento a Ignacio Zaragoza, Estadio Cuauhtémoc, Angelópolis y Vista panorámica de la ciudad. Escudo Otros nombres: El relicario de América/ La ciudad de los Ángeles/ La Angelópolis Lema: Muy noble y muy leal ciudad de Puebla de los Ángeles Heroica Puebla de Zaragoza Localización de Heroica Puebla de Zaragoza en México Heroica Puebla de Zaragoza Localización de Heroica Puebla de Zaragoza en Puebla Mapa interactivo Coordenadas 19°03′05″N 98°13′04″O  /  19.051388888889, -98.217777777778 Coordenadas: 19°03′05″N 98°13′04″O  /  19.051388888889, -98.217777777778 Idioma oficial Español Entidad Localidad  • País   México  • Estado Puebla  • Municipio Puebla Presidente municipal Claudia Rivera Vivanc...
            Read more

            Musa

            Image
            Para el género de plantas, véase Musa (planta). Apolo y la Nueve Musas En la mitología griega, las musas (en griego antiguo μοῦσαι « mousai» ) son, según los escritores más antiguos, las divinidades inspiradoras de las Artes: cada una de ellas está relacionada con ramas artísticas y del conocimiento. Son hijas de Zeus y de Mnemósine, compañeras del séquito de Apolo, dios olímpico de la música y patrón de las bellas artes, quien tuvo romances con cada una de ellas, dejando descendientes. Bajaban a la tierra a susurrar ideas e inspirar a aquellos mortales que las invocaran. En la época más arcaica eran las ninfas inspiradoras de las fuentes, en las cuales eran adoradas. Finalmente, alrededor de los siglos VIII-VII a. C. [ 1 ] ​ prevaleció en todo el territorio de la Hélade la adoración de las nueve Musas, que son Calíope, Clío, Erato, Euterpe, Melpómene, Polimnia, Talía, Terpsícore y Urania. El culto a las musas era originalmente de Tracia y Beocia, y fueron de vital impo...
            Read more