Find $\sum_{j=0}^{n}\sum_{i=j}^{n} {n \choose i}{i \choose j}$.
I don't know how to double summations like this very well. Can someone expand this to show how the $i=j$ thing works?
I tried the following:
${n \choose i}{i \choose j}={n \choose j}{n-j \choose i-j}$
$\sum_{j=0}^{n}\sum_{i=j}^{n} {n \choose i}{i \choose j}=\sum_{j=0}^{n}\sum_{i=j}^{n} {n \choose j}{n-j \choose i-j}=\sum_{j=0}^{n} {n \choose j}{n-j \choose 0}=2^n$
Where am I going wrong?
Best Answer
$$ \begin{align} \sum\limits_{i=j}^n\binom{n-j}{i-j} &=\sum\limits_{i=0}^{n-j}\binom{n-j}{i}\tag1\\[3pt] &=2^{n-j}\tag2 \end{align} $$ Explanation:
$(1)$: subsitute $i\mapsto i+j$
$(2)$: evaluate $(1+1)^{n-j}$ with the Binomial Theorem
If step $(1)$ is confusing, break it into two steps:
Thus, this sum is $2^{n-j}$, not $\binom{n-j}{0}$.
Now, the rest is evaluating either $$ 2^n\sum_{j=0}^n\color{#C00}{\binom{n}{j}}2^{-j}=2^n\left(1+2^{-1}\right)^n\tag{3a} $$ or $$ \sum_{j=0}^n\color{#C00}{\binom{n}{n-j}}2^{n-j}=(1+2)^n\tag{3b} $$ with the Binomial Theorem (the parts in red are equal).