Find $\sum_{i=0}^{n}\sum_{j=i}^n(\binom{n}{i}+\binom{n}{j})$

Question

Find $\sum_{i=0}^{n}\sum_{j=i}^n(\binom{n}{i}+\binom{n}{j})$

My working:

$$\sum_{i=0}^{n}\sum_{j=i}^n \left(\binom{n}{i}+\binom{n}{j}\right) =\frac{\sum_{i=0}^{n}\sum_{j=0}^n \left(\binom{n}{i}+\binom{n}{j}\right)-\sum_{i=0}^{n}\sum_{j=i} \left(\binom{n}{i}+\binom{n}{j}\right)}{2}$$

Now,
$$\sum_{i=0}^{n}\sum_{j=0}^n \left(\binom{n}{i}+\binom{n}{j} \right)=\sum_{i=0}^{n}n\binom{n}{i}+2^n=n2^n+n2^n=n2^{n+1}$$

and,
$$\sum_{i=0}^{n}\sum_{j=i}\left(\binom{n}{i}+\binom{n}{j}\right)=\sum_{i=0}^{n}2\binom{n}{i}=2\cdot 2^n=2^{n+1}$$

This gives us
$$\sum_{i=0}^{n}\sum_{j=i}^n \left(\binom{n}{i}+\binom{n}{j}\right)=\frac{n2^{n+1}-2^{n+1}}{2}=(n-1)2^n$$

But the correct answer is supposed to be $n2^n$ and I can't figure out what is wrong with my solution. It would be great if I could get a hint to find my error.

Answer 1

I think $n2^n$ is not the correct answer. Just check the simple case for $n=1$, which comes out to be \begin{align} &\bigg(\binom{1}{0}+\binom{1}{0}\bigg)+\bigg(\binom{1}{0}+\binom{1}{1}\bigg)+\bigg(\binom{1}{1}+\binom{1}{1}\bigg)\\ &=3 \times \bigg(\binom{1}{0}+\binom{1}{1}\bigg)=3 \times 2=(1+2) \times2^1 \end{align} Here's a trick which may prove fruitful here. $$\sum_{i=0}^n \sum_{j=i}^n a_{ij}=\sum_{j=0}^n \sum_{i=0}^j a_{ij}$$ We use this trick to compute the sum as follows. \begin{align} \sum_{i=0}^{n}\sum_{j=i}^n\bigg(\binom{n}{i}+\binom{n}{j}\bigg)&=\sum_{i=0}^{n}\sum_{j=i}^n\binom{n}{i}+\sum_{i=0}^{n}\sum_{j=i}^n\binom{n}{j}\\ &=\sum_{i=0}^{n}\sum_{j=i}^n\binom{n}{i}+\sum_{j=0}^{n}\sum_{i=0}^j\binom{n}{j}\\ &=\sum_{i=0}^{n}(n-i+1)\binom{n}{i}+\sum_{j=0}^{n}(j+1)\binom{n}{j}\\ &=\sum_{i=0}^{n}(n-i+1)\binom{n}{i}+\sum_{i=0}^{n}(i+1)\binom{n}{i}\\ &=\sum_{i=0}^{n}(n+2)\binom{n}{i}\\ &=(n+2)2^n \end{align}

Answer 2

You have made a small calculation mistake.

We have $$\sum_{i=0 }^{n} \sum_{j=0}^{n} \left(\binom{n}{i} + \binom {n}{j}\right) = 2 (n+1)2^n = (n+1)2^{n+1} $$

Putting this value gives us the correct result of $n\times 2^n $. Hope it helps.

Answer 3

Fix an integer $p$ with $0 \leq p \leq n$. Then $\binom{n}{p}$ appears $n-p + 1$ times as a term $\binom{n}{i}$ (when $i = p$ and $j = p, \dots, n$) and $p +1$ times as $\binom{n}{j}$ (for $i = 0, \dots, p$ and $j=p$). Thus it appears $n + 2$ times in all. Therefore $$\sum_{i=0}^n \sum_{j=i}^n \left[ \binom{n}{i} + \binom{n}{j} \right] = (n+2)\sum_{p=0}^n \binom{n}{p} = (n+2)2^n$$