Understanding summation formulas

Question

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.

Answer 1

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.