The following binomial coefficient identity holds for any integer n > 0. Xn k=0 n k n n k = 2n n Prove this identity combinatorially by interpreting both sides in terms of fixed density binary strings.

3. (8 points) The following binomial coefficient identity holds for any integer n> 0. 2n Prove this identity combinatorially by interpreting both sides in terms of fixed density binary strings