Is this summation$O(n^2)$? I think my summation is in $O(n^2)$ but I am not sure how to show it. How should I show that this summation $$\sum_{i=1}^n\sum_{j=i}^n(j-i)$$ is in $O(n^2)$?
 A: we know  


*

*$\sum_{i=b}^{n}{a}=(n-b+1)a$ (a and b are constant)

*$\sum_{i=a}^ni=\frac{(n-a+1)(n+a)}{2}$ (a is constant)
so
$$\sum_{i=1}^n\sum_{j=i}^n(j-i)=\sum_{i=1}^n(\sum_{j=i}^n(j-i))=\sum_{i=1}^n(\sum_{j=i}^nj-\sum_{j=i}^ni))$$
$$=\sum_{i=1}^n(\sum_{j=i}^nj-(n-i+1)i)$$
$$=\sum_{i=1}^n(\sum_{j=i}^nj-(ni-i^2+i))$$
$$=\sum_{i=1}^n(\frac{(n-i+1)(n+i)}{2}-ni+i^2-i)$$
$$=\sum_{i=1}^n(\frac{n^2-i^2+n+i}{2}-ni+i^2-i)$$
$$=\frac12\sum_{i=1}^n[(n^2+n)+i(-1-2n)+i^2]$$
$$=\frac12[n(n^2+n)+(-1-2n)\frac{n(n+1)}{2}+\frac16n(n+1)(2n+1)]$$
$$=\frac{n^3-n}{6}$$
so it's in $O(n^3)$
A: The summation counts the number of triples of integers $(i,j,k)$ satisfying $1 \le i < k < j+1 \le n+1$. (Fix $i,j$ and see that there are $j-i$ values of $k$ that can fit in between). So you should get $\binom{n+1}{3}$.
A: The sum is not zero, since all the numbers are non-negative, and some of them strictly positive. But you can sum it explicitly. Hint: you can do it using the formulas $$\sum_{i=1}^ni=\frac12n(n+1) \\ \sum_{i=1}^ni^2=\frac16n(n+1)(2n+1)$$ and the fact $\sum$ is linear.
