Finding sum of $\sum_{0\leq i<j\leq n} \binom{n}{i}$ and $\sum_{0\leq i<j\leq n}\binom{n}{j}$

Question

Finding sum of \begin{align} \sum_{0\leq i<j\leq n}\binom{n}{i} \tag1\\ \sum_{0\leq i<j\leq n}\binom{n}{j} \tag2 \end{align}

For $(1)$, we can write it as \begin{align} \sum_{0\leq i<j\leq n}\binom{n}{i} 1^j &= 1^1\binom{n}{0}+1^2\left[\binom{n}{0}+\binom{n}{1}\right]+1^3\left[\binom{n}{0}+\binom{n}{1}+\binom{n}{2}\right]+\cdots+\left[\binom{n}{0}+\binom{n}{1}+\cdots +\binom{n}{n-1}\right] \\ &=n\binom{n}{0}+(n-1)\binom{n}{1}+(n-2)\binom{n}{2}+\cdots +\binom{n}{n-1} \end{align}

How do I solve it after that?

Answer 1

We have $$\sum_{0\leq i<j\leq n}\binom{n}{i}=$$ $$n\binom{n}{0}+(n-1)\binom{n}{1}+(n-2)\binom{n}{2}+\cdots +\binom{n}{n-1}=$$ $$\sum_{i=0}^{n}(n-i)\binom{n}{i}= \sum_{i=0}^{n}(n-i)\binom{n}{n-i}= \sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1},$$ see, for instance, here for the last equality.

Also
$$\sum_{0\leq i<j\leq n}\binom{n}{j}=\sum_{j=0}^{n}j\binom{n}{j}=n2^{n-1}.$$

Answer 2

As you have done $$\sum_{0 \leq i \leq j \leq n} \binom{n}{i} = n\binom{n}{0} + (n-1)\binom{n}{1} + \cdots + \binom{n}{n-1}$$ Now we can rewrite it as $$\sum_{0 \leq i \leq j \leq n} \binom{n}{i} = \sum_{i=0}^{n-1} (n-i) \binom{n}{i} \tag{1}$$

We can also increase index of summation which is in RHS of $(1)$ because $(n-n)=0$ so,

$$\sum_{0 \leq i \leq j \leq n} \binom{n}{i} = \sum_{i=0}^{n} (n-i) \binom{n}{i} \tag{2}$$ $$\sum_{0 \leq i \leq j \leq n} \binom{n}{i} = n \underbrace{\sum_{i=0}^{n} \binom{n}{i}}_{s_1} - \underbrace{\sum_{i=0}^{n} i \binom{n}{i} }_{s_2} \tag{3}$$

Now we can easily find closed form for both summations in $(3)$, for that you can either see the linked questions in comments or use $$ (1+x)^n = \sum_{i=0}^{n}\binom{n}{i} x^i \tag{4} $$

Differentiate both sides of $(4)$ we get, $$ n (1+x)^n = \sum_{i=0}^{n}\binom{n}{i} i x^{i-1} $$

Now you can easily find the values of $s_1$ and $s_2$.