Prove that $\sum_{j=0}^{n}\sum_{i=j}^{n} {^nC_i} {^iC_j}=3^n$ Prove that
$$\sum_{j=0}^{n}\sum_{i=j}^{n} {^nC_i} \,{^iC_j}=3^n$$
I have tried by interchanging j by i but unable to prove. Don't know which combination formula would be used. Please help.
 A: Hints: 


*

*$\displaystyle \sum_{j=0}^n\sum_{i=j}^n=\sum_{i=0}^n\sum_{j=0}^i$

*$3=1+2$

*$2=1+1$
A: First, let $S_{ij}$ be the set of words $s$ in $\{0,1,2\}^n$ that satisfy both of the following 1. and 2. below:


*

*Precisely $n-i$ of the letters of $s$ are "0", oe equivalently, precisely $i$ letters of $s$ are in $\{1,2\}$.

*Of the $i$ letters that are in $\{1,2\}$, there are precsiely $j$ of those letters that are "2". 


(So $n-i$ letters of each $s \in S_{ij}$ are "0", $i-j$ letters of $s$ are "1", and the remaining $j$ letters of $s$ are "2".)
On the one hand: $|S_{ij}|= {^nC_i} \,{^iC_j}$; first choose the $(n-i)$ out of $n$ positions of $s$ such that the letter in each such position is "0", and then from the remaining $i$ positions, choose the $j$ positions such that the letter in each such position is a "2". On the other hand, the $S_{ij}$s partition $\{0,1,2\}^n$, which has cardinality $3^n$. So this gives 
$$3^n = \sum_{i=1}^n \sum_{j=1}^i |S_{ij}| =  \sum_{j=1}^n \sum_{i=j}^n |S_{ij}| = \sum_{j=1}^n\sum_{i=j}^n  {^nC_i} \,{^iC_j}.$$
