How to Reduce The Nested Sum $\sum_{j=1}^n\sum_{i=0}^{i<j} \frac{1}{2}$

I'm trying to find the expected number of swaps in a algorithm I'm working on. I've gotten to this point:

$E[S] =\sum_{j=1}^n\sum_{i=0}^{i<j} \frac{1}{2}$

I don't know how to reduce this further. The answer is supposed to be n(n-1)/4, but I don't know how to get there.

-

1 Answer

What you have actually simplifies to $\frac14n(n+1)$:

\begin{align*} \sum_{j=1}^n\sum_{i=0}^{j-1}\frac12&=\frac12\sum_{j=1}^n\sum_{i=0}^{j-1}1\\ &=\frac12\sum_{j=1}^nj&&\text{since there are }j\text{ terms}\\ &=\frac12\cdot\frac{n(n+1)}2&&\text{by the well-known formula}\\ &=\frac{n(n+1)}4\;. \end{align*}

If the inner sum started at $i=1$, you’d have $$\frac12\sum_{j=1}^n(j-1)=\frac12\sum_{k=0}^{n-1}k=\frac12\cdot\frac{(n-1)n}2=\frac{n(n-1)}4\;.$$

-
@Ryan Hurley: If you're wondering where you can find these properties, check out the wiki article: en.wikipedia.org/wiki/Summation#Identities –  anorton Oct 31 '12 at 1:50
Thank you so much...this is perfect! –  Ryan Hurley Oct 31 '12 at 1:53
@Ryan: You’re very welcome! –  Brian M. Scott Oct 31 '12 at 2:01