Double summation over binomial coefficients

Question

I tried to solve $\displaystyle \sum_{j=0}^{n} \sum_{i=j}^{n} \binom{n}{i} \binom{i}{j}$. Unfortunately, I cannot succeed in doing so. It comes with a hint that says: "Interchange the sums and first calculate $\displaystyle \sum_{j=0}^{i} \binom{i}{j}$ ". I do know how to solve this, but not how to come back to the original summation afterwards, since splitting up $\displaystyle \sum_{j=0}^{n}$ into $\displaystyle \sum_{j=0}^{i} + \sum_{j=i+1}^{n}$ results in an expression like $\displaystyle \sum_{i=j}^{n} \sum_{j=i+1}^{n}$ which I cannot make sense of.

Help would be appreciated.

Answer 1

Use $${n \choose i}{i \choose j}={n \choose j}{n-j \choose i-j}.$$ Then $$S=\displaystyle \sum_{j=0}^{n} \sum_{i=j}^{n} \binom{n}{i} \binom{i}{j}=\displaystyle \sum_{j=0}^{n}\binom{n}{j} \sum_{i=j}^{n}\binom{n-j}{i-j}.$$ Let $i-j=k$, then $$\implies S=\displaystyle \sum_{j=0}^{n}\binom{n}{j} \sum_{k=0}^{n-j}\binom{n-j}{k}=\sum_{j=0}^{n} {n \choose j} 2^{n-j}=2^n (1+1/2)^n=3^n.$$