Prove that ( 2 n n ) = ∑ k = 0 n ( n k ) 2 So far I have tried writing the right hand side in different ways: expressing it in its factorial form and have tried to implement the identity ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) but have not gained any new ground. If any one has an algebraic proof, or even a simple combinatorics proof that is intuitive and used with an example that would be preferable.

Question

Prove that                 (                      2        n            n                  )        =      ∑          k      =      0        n                            (                    n        k                          )              2   So far I have tried writing the right hand side in different ways: expressing it in its factorial form and have tried to implement the identity                (              n      k                  )        =                (                      n        −        1                    k        −        1                        )        +                (                      n        −        1            k                  )      but have not gained any new ground. If any one has an algebraic proof, or even a simple combinatorics proof that is intuitive and used with an example that would be preferable.

Boatein · Accepted Answer

(  1  +  x      )          2      n        =  (  1  +  x      )    n    (  1  +  x      )    n        ∑          k      =      0              2      n                      (                      2        n            k                  )            x    k    =            (              ∑                  k          =          0                n                                          (                          n          k                                  )                            x        k            )        2    =      ∑          k      =      0              2      n            x    k        ∑          i      =      0        k                  (              n      i                  )                      (              n              k        −        i                        )      The coefficient of       x    n   is                 (                      2        n            n                  )        =      ∑          i      =      0        n                  (              n      i                  )                      (              n              n        −        i                        )        =      ∑          i      =      0        n                              (                    n        i                          )              2  This is a special case of Vandermonde&#039;s identity.

Jaycee Mathis · Accepted Answer

To choose n people out of 2n people, first split the 2n people arbitrarily into 2 groups. Now, take k people from the first group and n-k people from the second group. If k is fixed, one can do this in                 (              n      k                  )                      (              n              n        −        k                        )        =                            (                    n        k                          )              2  . Summing over k to account for all possible k gives the result.

Prove that <mstyle scriptlevel="0"> <mo maxsize="2.047em" minsize="2.047em">(

Answered question

Answer & Explanation

New Questions in Precalculus