2

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?

gt6989b
  • 54,422
emaph
  • 23
  • It is the integral (sum) of a constant function. Therefore, it is the area (number of points) of the domain of integration. Look in the cube $[0,n-1]\times [0,n-2]\times[0,n-1]\subset \mathbb{Z}^3$ for the set $k\geq j+1$. Count how many points are there. – SphericalTriangle Mar 21 '18 at 16:18
  • Well for one, there is nothing depending on $i$, so you can get rid of the first sum with an $n$ factor. Then use linearity of the remaining sum. – Dave Mar 21 '18 at 16:22

4 Answers4

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

gt6989b
  • 54,422
CY Aries
  • 23,393
1

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?

Mohammad Riazi-Kermani
  • 68,728
1

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*}

Markus Scheuer
  • 108,315
0

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

Leyla Alkan
  • 2,451