Prove that $\sum_{j=0}^{n}\sum_{i=j}^{n} {^nC_i} {^iC_j}=3^n$

Question

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.

Answer 1

Hints:

• $\displaystyle \sum_{j=0}^n\sum_{i=j}^n=\sum_{i=0}^n\sum_{j=0}^i$
• $3=1+2$
• $2=1+1$

Answer 2

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:

1. Precisely $n-i$ of the letters of $s$ are "0", oe equivalently, precisely $i$ letters of $s$ are in $\{1,2\}$.
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}.$$