# Product of sum expression

I am having a little trouble following an example I came across today which says that:

$$2 \sum_{k=1}^{n} \sum_{i=0}^{k-2} 1 = 2 \sum_{k=1}^{n} (k-1) = 2 \sum_{j=0}^{n-1} j$$

I have tried fidgeting around with the expressions, but I just don't follow the thought process here. If anyone can please help me with some intermediate steps here, I will be very grateful!

-

Let's start by the interior summation, which is $$\sum_{i=0}^{k-2} 1=\underbrace{1+1+\cdots +1}_{k-1\, \text{times}},$$ k-1 times because there are the term when $i=0, i=1,\ldots , i=k-1$. So know you have $$2\sum_{k=1}^{n}(k-1)$$

Take $j=k-1$. When $k=1,j=0$ and when $k=n,j=n-1$, yielding $$2\sum_{j=0}^{n-1}j$$

Note that the $j=0$ term is useless, so you could always take it out, and you can explicitly calculate this sum with this formula: $$\sum_{j=1}^n j= \frac{n(n+1)}{2}.$$ In your case, one gets $$2\sum_{j=0}^{n-1}j=\frac{2(n-1)n}{2}=n(n-1)$$

-
Fantastic! Thanks a lot. It seems so easy now :) – Kristian Oct 2 '12 at 19:55
@Kristian Added some additional info – Jean-Sébastien Oct 2 '12 at 19:59

We will take each step one by one
$\sum_{i=0}^{k-2} 1 = k-1$
Now since we are summing up 1 $k-1$ times we can directly replace it with the term $k-1$. Consider the second part.
$\sum_{k=1}^n k-1$
Now put $j = k-1$ in the above equation we get
$\sum_{k=0}^{n-1} j$

-
Thank you very much. I really overcomplicated this in my notes! Now it looks so easy I almost feel ashamed for posting here! Really appreciate it! – Kristian Oct 2 '12 at 19:53

The first equality: You have $k-1$ summands (one for each $i=0, \ldots k-2$) of $1$, so you can replace the sum by $k-1$. The second equality: An index shift. Instead of adding up $k-1$ for $k=1, \ldots, n$, you add up $j$ for $j=0, \ldots n-1$.

-
A more encouraging starting line could be "It's not that difficult". =) – Pedro Tamaroff Oct 2 '12 at 19:49
Thank you very much! Yes, it seems so obvious now :). Really appreciate your help. – Kristian Oct 2 '12 at 19:54