How to explicit the summation

Question

I have the following summations:

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

and I know that the first step should be like this:

$$ \sum_{i = 0}^{n-1} \sum_{j = 0}^{n-2} (n - j - 1)$$

But I don't know how to get this. What is the mechanism?

Answer 1

$$ \sum_{i = 0}^{n-1} \sum_{j = 0}^{n-2} (n - j - 1)= n\cdot \sum_{j = 0}^{n-2} (n - j - 1)$$

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

Answer 2

Your first step is $$\sum\limits_{k =j+1}^{n-1} 1 = 1+1+1+...+1=(n-1)-(j)=n-j-1.$$

Now take the second step for$$ \sum\limits_{j = 0}^{n-2}(n - j - 1)= \sum\limits_{j = 0}^{n-2} n- \sum\limits_{j = 0}^{n-2} j-\sum\limits_{j = 0}^{n-2} 1 = \frac {n(n-1)}{2} $$

Can you finish The third step?

Answer 3

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

Let's first calculate this:$\sum_{k =j+1}^{n-1} 1$
When

• $k=j+1$, we get the result $1$
• $k=j+2$, we get the result $1$
  $\vdots$
• $k=n-1$, we get the result $1$
  So how many $1'$s we got here ? From $j+1$ to $n-1$ (including themselves) there are $(n-1-(j+1)+1=n-j-1)$ terms. Thus we got $1$ for each $n-j-1$ terms, thus the sum results $n-j-1$

---

$ \sum\limits_{i = 0}^{n-1} \sum\limits_{j = 0}^{n-2} (n - j - 1)= \sum\limits_{i = 0}^{n-1} [(n-1)+(n-2)+(n-3)+\cdots +1]=n[(n-1)+(n-2)+(n-3)+\cdots +1] $
(Similarly
when

• $i=0$, we get the result $[(n-1)+(n-2)+(n-3)+\cdots +1]$
• $i=1$, we get the result $[(n-1)+(n-2)+(n-3)+\cdots +1]$
  $\vdots$
• $i=n-1$, we get the result $[(n-1)+(n-2)+(n-3)+\cdots +1]$

So, we have here $n$ terms from $0$ to $n-1$ (including themselves) , calculated by $(n-1-0+1=n)$ . That iswe got $[(n-1)+(n-2)+(n-3)+\cdots +1]$ for each $n$ terms, thus the sum results $n[(n-1)+(n-2)+(n-3)+\cdots +1]$ )

Note also that $[(n-1)+(n-2)+(n-3)+\cdots +1]=1+2+3+\cdots +n-1= \frac {n(n-1)}{2}$
All in all, you get $$ \sum_{i = 0}^{n-1} \sum_{j = 0}^{n-2} \sum_{k =j+1}^{n-1} 1 =n[(n-1)+(n-2)+(n-3)+\cdots +1] = \frac {n^2(n-1)}{2}$$

Answer 4

Hint:

\begin{align*} \color{blue}{\sum_{k=j+1}^{n-1}1}=\sum_{k=1}^{n-1}1-\sum_{k=1}^j1\color{blue}{=n-1-j} \end{align*}