$\sum_{j=1}^n \sum_{k=j+1}^n (1)$

Question

This is an elementary question but somehow I am having a hard time seeing it. Can someone post a step by step why is it that:

$$\sum_{j=1}^n \sum_{k>j} \ (1) = \sum_{j=1}^n \sum_{k=j+1}^n (1) = \binom{n}{2} = \frac{1}{2} n(n-1)$$

Also could someone post a link to a pdf or a website where I can practice these? I looked online but could only find examples of cases where $n<10$.

Answer 1

$$\sum_{j=1}^n \sum_{k=j+1}^n 1=\sum_{j=1}^n (n-j)=n\sum_{j=1}^n 1-\sum_{j=1}^n j=n^2-\frac{1}{2} n (n+1)=\frac{1}{2} (n-1) n$$

Answer 2

$$\binom{n}{2}=\frac{n!}{2!(n-2)!}=\frac{n(n-1)(n-2)!}{2!(n-2)!}=\frac{n(n-1)}{2}$$

$$\sum_{k=1}^{j}1=j$$ $$\sum_{k=1}^{n}1=n$$ $$\sum_{k=1}^{n}1=\sum_{k=1}^{j}1+\sum_{k=j+1}^{n}1$$ $$\sum_{k=j+1}^{n}1=\sum_{k=1}^{n}1-\sum_{k=1}^{j}1=n-j$$

$$\sum_{j=1}^n \sum_{k=j+1}^{n} \ 1 =\sum_{j=1}^n\left(n-j\right)$$

Answer 3

How I see this is I start with $j = 1$ And so my next sum is $$\Sigma_{k = 2} ^{n} (1) = n-1$$ Now I'll add to this the value for when $j=2$, which will be $$\Sigma_{k = 3}^n (1) = n - 2$$. This pattern continues, so the nested sum you want is really just $$\Sigma_{i = 1}^n (n-i) = \Sigma_{i =1}^n(i) = \frac{1}{2} n(n-1)$$

Hope that helps!!