2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Nov 9, 2022 at 17:44
  • 2
    $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Nov 9, 2022 at 17:47
  • $\begingroup$ 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. $\endgroup$
    – 3rdMoment
    Nov 9, 2022 at 18:34

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you very much. It helped a lot and even makes sense xD $\endgroup$
    – TeamPhysics
    Nov 12, 2022 at 20:34
  • $\begingroup$ Now you can select this answer.. $\endgroup$
    – Z Ahmed
    Nov 13, 2022 at 1:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .