$\sum_{k+M = 0}^n {n \choose k} {n-k \choose m} = 3^n$ help with combinatorial reasoning

Question

$\sum_{k+M = 0}^n {n \choose k} {n-k \choose m} = 3^n $ I have worked the cases for $n=2$, $n=3$, and $n=4$ by hand and it appears to be true. $n=2$: $${2\choose 0}{2\choose 0} + {2\choose 1}{1\choose 0}+{2\choose 0}{2\choose 1}+{2\choose 0}{0\choose 0}+{2\choose 0}{2\choose 2}+{2\choose 1}{1\choose 1}=1+2+2+1+1+2=9=3^2.$$ Now I am unsure of how to use combinatorial reasoning in order to show this is true. I know 3^n is a r-permutation of n elements of 3 types, but I am having trouble with the left handside. any thougths on how to procede would be welcomed.

Answer 1

The left-hand side is $\sum_{k=0}^n\sum_{m=0}^{n-k} \dbinom{n}{k}\dbinom{n-k}{m}$. Combinatorially, first choose $k$ elements of the first type, then of the remaining $n-k$, choose $m$ elements of the second type. The remaining elements are of the third type. Summing over $m$ and $k$ gives all possibilities, so $3^n$.