# Double summation over binomial coefficients

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.

• A combinatorial proof is perhaps easiest here. Consider different methods of how you would count how many ways there are to partition $n$ objects up into $3$ labeled subsets. 1) Direct method. 2) Break into cases based on combined size of the first two subsets and picking what elements are used (unused go into third set), and then break into cases further based on size of first set and picking which elements go there. Nov 9, 2022 at 17:44
• As for the given hint, to visually see what is going on, consider drawing yourself a little picture. You'll have a triangular array of elements being added. One way of adding would be adding horizontally and then adding those subtotal results vertically afterwards. The other way might be adding vertically first, and then adding those subtotal results horizontally. In the end you should see something like $\sum\limits_{k=0}^n\binom{n}{k}2^k$ which you should recognize from binomial theorem. Nov 9, 2022 at 17:47
• The thing to notice is that lots of your terms in the original sum have $j>i$, which means $i \choose j$ is zero and those terms drop out. Nov 9, 2022 at 18:34

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.$$