Find $\sum_{j=0}^{n}\sum_{i=j}^{n} {n \choose i}{i \choose j}$.

binomial-coefficientscombinatoricssummation

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:

  1. $i\mapsto k+j$: since $i$ ranges from $j$ to $n$, $k=i-j$ ranges from $0$ to $n-j$
  2. $k\mapsto i$: simply change the variable of summation back

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

Related Question