Prove that $binom{n}{1}^2+2binom{n}{2}^2+cdots +nbinom{n}{n}^2=nbinom{2n-1}{n-1}$











up vote
1
down vote

favorite
1













Prove that
$$
binom{n}{1}^2+2binom{n}{2}^2+cdots + nbinom{n}{n}^2
= n binom{2n-1}{n-1}.
$$




So
$$
sum_{k=1}^n k binom{n}{k}^2
= sum_{k=1}^n k binom{n}{k}binom{n}{k}
= sum_{k=1}^n n binom{n-1}{k-1} binom{n}{k}
= n sum_{k=0}^{n-1} frac{(n-1)!n!}{(n-k-1)!k!(n-k-1)!(k+1)!}
= n^2 sum_{k=0}^{n-1} frac{(n-1)!^2}{(n-k-1)!^2k!^2(k+1)}
=n^2 sum_{k=0}^{n-1} binom{n-1}{k}^2frac{1}{k+1}.
$$

I do not know what to do with $frac{1}{k+1}$, how to get rid of that.










share|cite|improve this question




























    up vote
    1
    down vote

    favorite
    1













    Prove that
    $$
    binom{n}{1}^2+2binom{n}{2}^2+cdots + nbinom{n}{n}^2
    = n binom{2n-1}{n-1}.
    $$




    So
    $$
    sum_{k=1}^n k binom{n}{k}^2
    = sum_{k=1}^n k binom{n}{k}binom{n}{k}
    = sum_{k=1}^n n binom{n-1}{k-1} binom{n}{k}
    = n sum_{k=0}^{n-1} frac{(n-1)!n!}{(n-k-1)!k!(n-k-1)!(k+1)!}
    = n^2 sum_{k=0}^{n-1} frac{(n-1)!^2}{(n-k-1)!^2k!^2(k+1)}
    =n^2 sum_{k=0}^{n-1} binom{n-1}{k}^2frac{1}{k+1}.
    $$

    I do not know what to do with $frac{1}{k+1}$, how to get rid of that.










    share|cite|improve this question


























      up vote
      1
      down vote

      favorite
      1









      up vote
      1
      down vote

      favorite
      1






      1






      Prove that
      $$
      binom{n}{1}^2+2binom{n}{2}^2+cdots + nbinom{n}{n}^2
      = n binom{2n-1}{n-1}.
      $$




      So
      $$
      sum_{k=1}^n k binom{n}{k}^2
      = sum_{k=1}^n k binom{n}{k}binom{n}{k}
      = sum_{k=1}^n n binom{n-1}{k-1} binom{n}{k}
      = n sum_{k=0}^{n-1} frac{(n-1)!n!}{(n-k-1)!k!(n-k-1)!(k+1)!}
      = n^2 sum_{k=0}^{n-1} frac{(n-1)!^2}{(n-k-1)!^2k!^2(k+1)}
      =n^2 sum_{k=0}^{n-1} binom{n-1}{k}^2frac{1}{k+1}.
      $$

      I do not know what to do with $frac{1}{k+1}$, how to get rid of that.










      share|cite|improve this question
















      Prove that
      $$
      binom{n}{1}^2+2binom{n}{2}^2+cdots + nbinom{n}{n}^2
      = n binom{2n-1}{n-1}.
      $$




      So
      $$
      sum_{k=1}^n k binom{n}{k}^2
      = sum_{k=1}^n k binom{n}{k}binom{n}{k}
      = sum_{k=1}^n n binom{n-1}{k-1} binom{n}{k}
      = n sum_{k=0}^{n-1} frac{(n-1)!n!}{(n-k-1)!k!(n-k-1)!(k+1)!}
      = n^2 sum_{k=0}^{n-1} frac{(n-1)!^2}{(n-k-1)!^2k!^2(k+1)}
      =n^2 sum_{k=0}^{n-1} binom{n-1}{k}^2frac{1}{k+1}.
      $$

      I do not know what to do with $frac{1}{k+1}$, how to get rid of that.







      discrete-mathematics binomial-coefficients






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Nov 17 at 9:53









      Viktor Glombik

      489321




      489321










      asked Nov 17 at 8:52









      Marko Škorić

      69810




      69810






















          4 Answers
          4






          active

          oldest

          votes

















          up vote
          2
          down vote



          accepted










          $$sum_{k=1}^{n}kbinom{n}{k}^{2}=nsum_{k=1}^{n}binom{n-1}{k-1}binom{n}{n-k}=nsum_{k=0}^{n-1}binom{n-1}{k}binom{n}{n-k-1}=nbinom{2n-1}{n-1}$$



          Applying Vandermonde's identity in third equality.






          share|cite|improve this answer




























            up vote
            3
            down vote













            A combinatorial proof:



            We have $n$ men and $n$ women and I want to choose a $n$-person committee and a committee president among those, with the condition that the president must be a woman.



            One way to do that is to choose a president among the $n$ women and then choose $n-1$ committee members from the remaining $2n-1$ persons.



            So that way gives $n binom{2n-1}{n-1}$ ways, the right hand side.



            On the other hand I can split the count on the number of women in the committee, so there can be $i=1,2,ldots,n$ many women.



            To count those for a fixed $i$, first pick the $i$ women in $binom{n}{i}$ ways, pick the president among those in $i$ ways, and then pick the men in $binom{n}{n-i} = binom{n}{i}$ ways. So for a fixed $i$ we have $i binom{n}{i}^2$ committees with $i$ women. Summing them gives us the left hand side.






            share|cite|improve this answer






























              up vote
              1
              down vote













              We present a slight variation using formal power series and the
              coefficient-of operator. Starting from



              $$sum_{k=1}^n k {nchoose k}^2
              = sum_{k=1}^n k {nchoose k} [z^{n-k}] (1+z)^n
              \ = [z^n] (1+z)^n sum_{k=1}^n k {nchoose k} z^k
              = n [z^n] (1+z)^n sum_{k=1}^n {n-1choose k-1} z^k
              \ = n [z^n] z (1+z)^n sum_{k=0}^{n-1} {n-1choose k} z^k
              = n [z^{n-1}] (1+z)^n (1+z)^{n-1}
              \ = n [z^{n-1}] (1+z)^{2n-1} = n times {2n-1choose n-1}$$



              which is the claim.






              share|cite|improve this answer






























                up vote
                0
                down vote













                $$k binom nk^2=binom nkcdot kbinom nk$$



                For $kge1,$ $$kbinom nk=kcdotdfrac{n!}{k!cdot(n-k)!}=ndfrac{(n-1)!}{(k-1)!{n-1-(k-1)}!}=nbinom{n-1}{k-1}$$



                Now in the identity $(1+x)^{2n-1}=(x+1)^n(1+x)^{n-1},$ compare coefficients of $x^n$



                $$binom{2n-1}n=sum_{k=0}^nbinom nkbinom{n-1}{k-1}$$






                share|cite|improve this answer





















                  Your Answer





                  StackExchange.ifUsing("editor", function () {
                  return StackExchange.using("mathjaxEditing", function () {
                  StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
                  StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
                  });
                  });
                  }, "mathjax-editing");

                  StackExchange.ready(function() {
                  var channelOptions = {
                  tags: "".split(" "),
                  id: "69"
                  };
                  initTagRenderer("".split(" "), "".split(" "), channelOptions);

                  StackExchange.using("externalEditor", function() {
                  // Have to fire editor after snippets, if snippets enabled
                  if (StackExchange.settings.snippets.snippetsEnabled) {
                  StackExchange.using("snippets", function() {
                  createEditor();
                  });
                  }
                  else {
                  createEditor();
                  }
                  });

                  function createEditor() {
                  StackExchange.prepareEditor({
                  heartbeatType: 'answer',
                  convertImagesToLinks: true,
                  noModals: true,
                  showLowRepImageUploadWarning: true,
                  reputationToPostImages: 10,
                  bindNavPrevention: true,
                  postfix: "",
                  imageUploader: {
                  brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
                  contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
                  allowUrls: true
                  },
                  noCode: true, onDemand: true,
                  discardSelector: ".discard-answer"
                  ,immediatelyShowMarkdownHelp:true
                  });


                  }
                  });














                  draft saved

                  draft discarded


















                  StackExchange.ready(
                  function () {
                  StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3002114%2fprove-that-binomn122-binomn22-cdots-n-binomnn2-n-binom2n-1%23new-answer', 'question_page');
                  }
                  );

                  Post as a guest















                  Required, but never shown

























                  4 Answers
                  4






                  active

                  oldest

                  votes








                  4 Answers
                  4






                  active

                  oldest

                  votes









                  active

                  oldest

                  votes






                  active

                  oldest

                  votes








                  up vote
                  2
                  down vote



                  accepted










                  $$sum_{k=1}^{n}kbinom{n}{k}^{2}=nsum_{k=1}^{n}binom{n-1}{k-1}binom{n}{n-k}=nsum_{k=0}^{n-1}binom{n-1}{k}binom{n}{n-k-1}=nbinom{2n-1}{n-1}$$



                  Applying Vandermonde's identity in third equality.






                  share|cite|improve this answer

























                    up vote
                    2
                    down vote



                    accepted










                    $$sum_{k=1}^{n}kbinom{n}{k}^{2}=nsum_{k=1}^{n}binom{n-1}{k-1}binom{n}{n-k}=nsum_{k=0}^{n-1}binom{n-1}{k}binom{n}{n-k-1}=nbinom{2n-1}{n-1}$$



                    Applying Vandermonde's identity in third equality.






                    share|cite|improve this answer























                      up vote
                      2
                      down vote



                      accepted







                      up vote
                      2
                      down vote



                      accepted






                      $$sum_{k=1}^{n}kbinom{n}{k}^{2}=nsum_{k=1}^{n}binom{n-1}{k-1}binom{n}{n-k}=nsum_{k=0}^{n-1}binom{n-1}{k}binom{n}{n-k-1}=nbinom{2n-1}{n-1}$$



                      Applying Vandermonde's identity in third equality.






                      share|cite|improve this answer












                      $$sum_{k=1}^{n}kbinom{n}{k}^{2}=nsum_{k=1}^{n}binom{n-1}{k-1}binom{n}{n-k}=nsum_{k=0}^{n-1}binom{n-1}{k}binom{n}{n-k-1}=nbinom{2n-1}{n-1}$$



                      Applying Vandermonde's identity in third equality.







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Nov 17 at 8:59









                      drhab

                      95.1k543126




                      95.1k543126






















                          up vote
                          3
                          down vote













                          A combinatorial proof:



                          We have $n$ men and $n$ women and I want to choose a $n$-person committee and a committee president among those, with the condition that the president must be a woman.



                          One way to do that is to choose a president among the $n$ women and then choose $n-1$ committee members from the remaining $2n-1$ persons.



                          So that way gives $n binom{2n-1}{n-1}$ ways, the right hand side.



                          On the other hand I can split the count on the number of women in the committee, so there can be $i=1,2,ldots,n$ many women.



                          To count those for a fixed $i$, first pick the $i$ women in $binom{n}{i}$ ways, pick the president among those in $i$ ways, and then pick the men in $binom{n}{n-i} = binom{n}{i}$ ways. So for a fixed $i$ we have $i binom{n}{i}^2$ committees with $i$ women. Summing them gives us the left hand side.






                          share|cite|improve this answer



























                            up vote
                            3
                            down vote













                            A combinatorial proof:



                            We have $n$ men and $n$ women and I want to choose a $n$-person committee and a committee president among those, with the condition that the president must be a woman.



                            One way to do that is to choose a president among the $n$ women and then choose $n-1$ committee members from the remaining $2n-1$ persons.



                            So that way gives $n binom{2n-1}{n-1}$ ways, the right hand side.



                            On the other hand I can split the count on the number of women in the committee, so there can be $i=1,2,ldots,n$ many women.



                            To count those for a fixed $i$, first pick the $i$ women in $binom{n}{i}$ ways, pick the president among those in $i$ ways, and then pick the men in $binom{n}{n-i} = binom{n}{i}$ ways. So for a fixed $i$ we have $i binom{n}{i}^2$ committees with $i$ women. Summing them gives us the left hand side.






                            share|cite|improve this answer

























                              up vote
                              3
                              down vote










                              up vote
                              3
                              down vote









                              A combinatorial proof:



                              We have $n$ men and $n$ women and I want to choose a $n$-person committee and a committee president among those, with the condition that the president must be a woman.



                              One way to do that is to choose a president among the $n$ women and then choose $n-1$ committee members from the remaining $2n-1$ persons.



                              So that way gives $n binom{2n-1}{n-1}$ ways, the right hand side.



                              On the other hand I can split the count on the number of women in the committee, so there can be $i=1,2,ldots,n$ many women.



                              To count those for a fixed $i$, first pick the $i$ women in $binom{n}{i}$ ways, pick the president among those in $i$ ways, and then pick the men in $binom{n}{n-i} = binom{n}{i}$ ways. So for a fixed $i$ we have $i binom{n}{i}^2$ committees with $i$ women. Summing them gives us the left hand side.






                              share|cite|improve this answer














                              A combinatorial proof:



                              We have $n$ men and $n$ women and I want to choose a $n$-person committee and a committee president among those, with the condition that the president must be a woman.



                              One way to do that is to choose a president among the $n$ women and then choose $n-1$ committee members from the remaining $2n-1$ persons.



                              So that way gives $n binom{2n-1}{n-1}$ ways, the right hand side.



                              On the other hand I can split the count on the number of women in the committee, so there can be $i=1,2,ldots,n$ many women.



                              To count those for a fixed $i$, first pick the $i$ women in $binom{n}{i}$ ways, pick the president among those in $i$ ways, and then pick the men in $binom{n}{n-i} = binom{n}{i}$ ways. So for a fixed $i$ we have $i binom{n}{i}^2$ committees with $i$ women. Summing them gives us the left hand side.







                              share|cite|improve this answer














                              share|cite|improve this answer



                              share|cite|improve this answer








                              edited Nov 17 at 9:46

























                              answered Nov 17 at 9:10









                              Henno Brandsma

                              102k345109




                              102k345109






















                                  up vote
                                  1
                                  down vote













                                  We present a slight variation using formal power series and the
                                  coefficient-of operator. Starting from



                                  $$sum_{k=1}^n k {nchoose k}^2
                                  = sum_{k=1}^n k {nchoose k} [z^{n-k}] (1+z)^n
                                  \ = [z^n] (1+z)^n sum_{k=1}^n k {nchoose k} z^k
                                  = n [z^n] (1+z)^n sum_{k=1}^n {n-1choose k-1} z^k
                                  \ = n [z^n] z (1+z)^n sum_{k=0}^{n-1} {n-1choose k} z^k
                                  = n [z^{n-1}] (1+z)^n (1+z)^{n-1}
                                  \ = n [z^{n-1}] (1+z)^{2n-1} = n times {2n-1choose n-1}$$



                                  which is the claim.






                                  share|cite|improve this answer



























                                    up vote
                                    1
                                    down vote













                                    We present a slight variation using formal power series and the
                                    coefficient-of operator. Starting from



                                    $$sum_{k=1}^n k {nchoose k}^2
                                    = sum_{k=1}^n k {nchoose k} [z^{n-k}] (1+z)^n
                                    \ = [z^n] (1+z)^n sum_{k=1}^n k {nchoose k} z^k
                                    = n [z^n] (1+z)^n sum_{k=1}^n {n-1choose k-1} z^k
                                    \ = n [z^n] z (1+z)^n sum_{k=0}^{n-1} {n-1choose k} z^k
                                    = n [z^{n-1}] (1+z)^n (1+z)^{n-1}
                                    \ = n [z^{n-1}] (1+z)^{2n-1} = n times {2n-1choose n-1}$$



                                    which is the claim.






                                    share|cite|improve this answer

























                                      up vote
                                      1
                                      down vote










                                      up vote
                                      1
                                      down vote









                                      We present a slight variation using formal power series and the
                                      coefficient-of operator. Starting from



                                      $$sum_{k=1}^n k {nchoose k}^2
                                      = sum_{k=1}^n k {nchoose k} [z^{n-k}] (1+z)^n
                                      \ = [z^n] (1+z)^n sum_{k=1}^n k {nchoose k} z^k
                                      = n [z^n] (1+z)^n sum_{k=1}^n {n-1choose k-1} z^k
                                      \ = n [z^n] z (1+z)^n sum_{k=0}^{n-1} {n-1choose k} z^k
                                      = n [z^{n-1}] (1+z)^n (1+z)^{n-1}
                                      \ = n [z^{n-1}] (1+z)^{2n-1} = n times {2n-1choose n-1}$$



                                      which is the claim.






                                      share|cite|improve this answer














                                      We present a slight variation using formal power series and the
                                      coefficient-of operator. Starting from



                                      $$sum_{k=1}^n k {nchoose k}^2
                                      = sum_{k=1}^n k {nchoose k} [z^{n-k}] (1+z)^n
                                      \ = [z^n] (1+z)^n sum_{k=1}^n k {nchoose k} z^k
                                      = n [z^n] (1+z)^n sum_{k=1}^n {n-1choose k-1} z^k
                                      \ = n [z^n] z (1+z)^n sum_{k=0}^{n-1} {n-1choose k} z^k
                                      = n [z^{n-1}] (1+z)^n (1+z)^{n-1}
                                      \ = n [z^{n-1}] (1+z)^{2n-1} = n times {2n-1choose n-1}$$



                                      which is the claim.







                                      share|cite|improve this answer














                                      share|cite|improve this answer



                                      share|cite|improve this answer








                                      edited Nov 18 at 16:13

























                                      answered Nov 18 at 13:31









                                      Marko Riedel

                                      38.5k339106




                                      38.5k339106






















                                          up vote
                                          0
                                          down vote













                                          $$k binom nk^2=binom nkcdot kbinom nk$$



                                          For $kge1,$ $$kbinom nk=kcdotdfrac{n!}{k!cdot(n-k)!}=ndfrac{(n-1)!}{(k-1)!{n-1-(k-1)}!}=nbinom{n-1}{k-1}$$



                                          Now in the identity $(1+x)^{2n-1}=(x+1)^n(1+x)^{n-1},$ compare coefficients of $x^n$



                                          $$binom{2n-1}n=sum_{k=0}^nbinom nkbinom{n-1}{k-1}$$






                                          share|cite|improve this answer

























                                            up vote
                                            0
                                            down vote













                                            $$k binom nk^2=binom nkcdot kbinom nk$$



                                            For $kge1,$ $$kbinom nk=kcdotdfrac{n!}{k!cdot(n-k)!}=ndfrac{(n-1)!}{(k-1)!{n-1-(k-1)}!}=nbinom{n-1}{k-1}$$



                                            Now in the identity $(1+x)^{2n-1}=(x+1)^n(1+x)^{n-1},$ compare coefficients of $x^n$



                                            $$binom{2n-1}n=sum_{k=0}^nbinom nkbinom{n-1}{k-1}$$






                                            share|cite|improve this answer























                                              up vote
                                              0
                                              down vote










                                              up vote
                                              0
                                              down vote









                                              $$k binom nk^2=binom nkcdot kbinom nk$$



                                              For $kge1,$ $$kbinom nk=kcdotdfrac{n!}{k!cdot(n-k)!}=ndfrac{(n-1)!}{(k-1)!{n-1-(k-1)}!}=nbinom{n-1}{k-1}$$



                                              Now in the identity $(1+x)^{2n-1}=(x+1)^n(1+x)^{n-1},$ compare coefficients of $x^n$



                                              $$binom{2n-1}n=sum_{k=0}^nbinom nkbinom{n-1}{k-1}$$






                                              share|cite|improve this answer












                                              $$k binom nk^2=binom nkcdot kbinom nk$$



                                              For $kge1,$ $$kbinom nk=kcdotdfrac{n!}{k!cdot(n-k)!}=ndfrac{(n-1)!}{(k-1)!{n-1-(k-1)}!}=nbinom{n-1}{k-1}$$



                                              Now in the identity $(1+x)^{2n-1}=(x+1)^n(1+x)^{n-1},$ compare coefficients of $x^n$



                                              $$binom{2n-1}n=sum_{k=0}^nbinom nkbinom{n-1}{k-1}$$







                                              share|cite|improve this answer












                                              share|cite|improve this answer



                                              share|cite|improve this answer










                                              answered Nov 17 at 10:10









                                              lab bhattacharjee

                                              221k15155272




                                              221k15155272






























                                                  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%2f3002114%2fprove-that-binomn122-binomn22-cdots-n-binomnn2-n-binom2n-1%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

                                                  Puebla de Zaragoza

                                                  Musa