Prove using the method of double counting: $3^n =\sum_{k=0}^n \dbinom{n}{k} \sum_{j=0}^k \dbinom{k}{j}$ [duplicate]

Solution 1:

We will use the identity $$ \binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}\quad (n\geq k\geq r\geq 0). $$ Interchange the order of summation and use the identity above to get that $$ \sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} =\sum_{r=0}^{n}\binom{n}{r}\sum_{k=r}^{n}\binom{n-r}{k-r}=\sum_{r=0}^n\binom{n}{r}2^{n-r}=(1+2)^n=3^n $$ where we used the fact that $$ \sum_{k=r}^{n}\binom{n-r}{k-r}=\sum_{u=0}^{n-r}\binom{n-r}{u}=2^{n-r}. $$

Solution 2:

You know that $\displaystyle(1+x)^n=\sum_{k=0}^n\binom nkx^k$

$\displaystyle\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} =\sum_{k=0}^{n}\binom{n}{k}\sum_{r=0}^{k} \binom{k}{r}=\sum_{k=0}^{n}\binom{n}{k}\sum_{r=0}^{k} \binom{k}{r}1^r$

Since $\displaystyle\sum_{r=0}^{k} \binom{k}{r}1^r=(1+1)^k=2^k$, we have

$\displaystyle\implies\sum_{k=0}^{n} \binom nk2^k=(1+2)^n=3^n$