Q:

Understanding summation formulas

Can someone help me to understand what is going on here because I have some misunderstanding about some summation formulas of constant
1) Why we can write this constant summation like below? Some explanation and citation.
$$\sum_{k=j+1}^{n-1}c=\sum_{i=m}^{n}1={n-m+1}$$ 
Step 1) $$\sum_{k=j+1}^{n-1}c={(n-1)-(j+1)+1}={n-1-j-1+1}={n-j-1}$$ 
Step 2)
$$c\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}({n-j-1)}=c\sum_{i=0}^{n-1}\left[\sum_{j=i+1}^{n-1}n - \sum_{j=i+1}^{n-1}j-\sum_{j=i+1}^{n-1}1\right]$$ 
Step 3) For each summation in brackets we continue:
$$\sum_{j=i+1}^{n-1}n = n\sum_{j=i+1}^{n-1}=n((n-1) - (i+1)+1) = n(n-1-i)$$
$$\sum_{j=i+1}^{n-1}j = \sum_{i=1}^{n}i=\frac{n^{2}+n}{2}=\frac{(n-1)^{2}+n-1}{2} = \frac{n^{2}-n}{2}$$
At this point I don't understand why is there some other result for this one like:
$$\frac{(n-1-i)(n+1)}{2}$$
Some table of formulas and examples for problems to find big-Oh notation would be perfect.

A:

Hint: The representation $\sum_{k=j+1}^{n-1}c=\sum_{i=m}^{n}1={n-m+1}$ is not admissible.

We obtain
  \begin{align*}
T(n)&=\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\color{blue}{\sum_{k=j+1}^{n-1}c}\\
&=\color{blue}{c}\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\color{blue}{\sum_{k=j+1}^{n-1}1}\\
&=\color{blue}{c}\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\color{blue}{(n-j-1)}
\end{align*}

Here is a slightly different derivation which might ease calculations.

At first we observe that the upper limits $n-1$ lead to factors $n-1$ during the calculation. This can be simplified if we calculate $T(n+1)$ instead of $T(n)$. The formula for $T(n)$ can then be easily derived from $T(n+1)$.
We obtain
  \begin{align*}
\color{blue}{T(n+1)}&=\sum_{i=0}^{n}\sum_{j=i+1}^{n}\sum_{k=j+1}^{n}c\\
&=c\sum_{i=0}^{n}\sum_{j=i+1}^{n}\sum_{k=j+1}^{n}1\tag{1}\\
&=c\sum_{i=0}^{n}\sum_{j=i+1}^{n}(n-j)\tag{2}\\
&=c\sum_{i=0}^{n}\sum_{j=0}^{n-i-1}(n-j-i-1)\tag{3}\\
&=c\sum_{i=0}^{n}\sum_{j=0}^{n-i-1}j\tag{4}\\
&=c\sum_{i=0}^{n}\frac{1}{2}(n-i-1)(n-i)\tag{5}\\
&=\frac{c}{2}\sum_{i=0}^{n}(i-1)i\tag{6}\\
&=\frac{c}{2}\left[\frac{1}{6}n(n+1)(2n+1)-\frac{1}{2}n(n+1)\right]\tag{7}\\
&\color{blue}{=\frac{c}{6}\left(n^3-n\right)}
\end{align*}

Comment:

In (1) we factor out the constant $c$.
In (2) we calculate the inner sum.
In (3) we shift the index of the inner sum to start with $j=0$.
In (4) we change the order of summation of the inner sum $j\rightarrow n-i-1-j$.
In (5) we calculate the inner sum by recalling Faulhaber's formulas.
In (6) we again change the order of summation of the inner sum $i \rightarrow n-i$. More detailed:
\begin{align*}
c\sum_{i=0}^{n}\frac{1}{2}(n-i-1)(n-i)
&=\frac{c}{2}\sum_{i=0}^{n}(n-i-1)(n-i)\\
&=\frac{c}{2}\sum_{i=0}^{n}(n-(n-i)-1)(n-(n-i))\qquad\qquad\qquad [i\rightarrow n-i]\\
&=\frac{c}{2}\sum_{i=0}^{n}(i-1)i
\end{align*}
In (7) we again use Faulhaber's formulas.

