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.4k93355




43.4k93355










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

        49.9k457119




        49.9k457119























            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.7k339107




            38.7k339107












            • 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

            Bressuire

            Image
            .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid
            Read more

            Cabo Verde

            Image
              Nota: Cabo-verdiano redireciona para este artigo. Para a língua falada em Cabo Verde, veja crioulo cabo-verdiano. Para outros significados, veja Cabo Verde (desambiguação). Coordenadas: 14° 55' N 23° 31' O Cabo Verde República de Cabo Verde Bandeira Brasão de Armas Lema: Unidade, Trabalho, Progresso Hino nacional: Cântico da Liberdade Gentílico: cabo-verdiano [ 1 ] Capital Praia 14° 55' N 23° 31' O Cidade mais populosa Praia Língua oficial Português Governo República unitária semipresidencialista [ 2 ]  - Presidente Jorge Carlos Fonseca  - Primeiro-ministro Ulisses Correia e Silva História    - Descoberta 1460   - Independência 00 • de Portugal 5 de Julho de 1975   - Multipartidarismo 13 de Janeiro de 1990  Área    - Total 4 033 km² (146.º)  - Água (%) 0,08 População    - Estimativa para 2017 560 899 [ 3 ] hab. (173.º)
            Read more

            Gyllenstierna

            Image
            .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid
            Read more