Discrete math combinatorial proofProve that for every positive integer n, ∑ k = 0 n ( n k ) 2 = ∑ l = 0 n ∑ r = 0 n − l 2 ( n l ) ( n − l r ) ( n − l − r r ) I know that ∑ k = 0 n ( n k ) 2 = ( 2 n n ) but I can't seem to find a way to connect it to the right side.

Question

Discrete math combinatorial proofProve that for every positive integer n,       ∑          k      =      0              n                                    (                            n        k                              )                      2    =      ∑          l      =      0              n            ∑          r      =      0                                n          −          l                2                                (                    n      l                      )                                (                            n        −        l            r                      )                                (                            n        −        l        −        r            r                      )            I know that       ∑          k      =      0              n                                    (                            n        k                              )                      2    =                    (                            2        n            n                      )             but I can&#039;t seem to find a way to connect it to the right side.

Tamoni5e · Accepted Answer

Step 1The lefthand side is the number of pairs ⟨A,B⟩ such that A and B are subsets of   [  n  ]  =  {  1  ,  …  ,  n  }, and       |    A      |    =      |    B      |  .Step 2You can classify these pairs according to the number of elements that they have in common. Suppose that   C  =  A  ∩  B; then A∖C and B∖C must be disjoint subsets of [n]. Think of setting   ℓ  =      |    C      |   and   r  =      |    A  ∖  C      |    =      |    A  ∖  B      |  .