Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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) $$

share|improve this answer
    
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$

share|improve this answer
    
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$.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.