1
$\begingroup$

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!

3 Answers 3

3

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

  • 0
    Thank you very much! Yes, it seems so obvious now :). Really appreciate your help.2012-10-02
4

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$

  • 0
    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!2012-10-02
4

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

  • 0
    @Kristian Added some additional info2012-10-02