3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ please don't edit the question again and again remove that c you added after answering the question $\endgroup$ – Deepesh Meena Sep 3 '18 at 3:07
4
$\begingroup$

$$\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$$

$\endgroup$
1
$\begingroup$

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!!

$\endgroup$
1
$\begingroup$

$$\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)$$

$\endgroup$
  • $\begingroup$ I know. I am asking about the summation steps. Thanks. $\endgroup$ – Note Sep 3 '18 at 3:01
  • $\begingroup$ I think you meant $\sum_{k=1}^j k = \frac{j(j+1)}{2}$ not $\sum_{k=1}^j 1$. $\endgroup$ – Note Sep 3 '18 at 3:23
  • 1
    $\begingroup$ yup sorry I will edit it $\endgroup$ – Deepesh Meena Sep 3 '18 at 3:24
  • 1
    $\begingroup$ Is that fine now $\endgroup$ – Deepesh Meena Sep 3 '18 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.