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'm sure this is a really simple question but I have a series and I'm sure it has a name but my math is rusty and I'm not sure what it is.

$$ \sum_{i=0}^{N} (N - i)$$

I have an algorithm which has execution time characterized by this function and I'm wondering what to call it.

share|improve this question
1  
It's just the sum $1+2+3+\cdots+N$. –  David Mitra Apr 29 '12 at 3:40
    
@DavidMitra yeah, does that have a name? –  Luke McGregor Apr 29 '12 at 3:40
2  
Arithmetic progression. –  David Mitra Apr 29 '12 at 3:41

2 Answers 2

up vote 7 down vote accepted

This is an arithmetic progression with base $N$ and common difference $-1$.

As it happens, it equals $0+1+2+\cdots+N$, whose sum is well known to be $N(N+1)/2$.

In general, an arithmetic progression with base $a$ and common difference $b$ is a sequence of the form $$a,\ a+b,\ a+2b,\ a+3b,\ldots$$

The sum of the terms $a$, $a+b$, $a+2b,\ldots,a+nb$ is $$\begin{align*} a+(a+b)+(a+2b)+\cdots + (a+nb) &= \underbrace{a+a+\cdots+a}_{n+1\text{ summands}} + (b+2b+\cdots+nb)\\ &= (n+1)a + b(1+2+\cdots+n)\\ &= (n+1)a + b\left(\frac{n(n+1)}{2}\right)\\ &= (n+1)\left( a + \frac{bn}{2}\right). \end{align*}$$ (of course, this uses the fact that $1+2+\cdots+n=\frac{n(n+1)}{2}$; there are many proofs of this: see this previous post)

In your case, with $a=N$, $b=-1$, and $n=N$, we would have $$(N+1)\left(N -\frac{N}{2}\right) = \frac{N(N+1)}{2},$$ as before.

share|improve this answer
    
Thats awesome, thanks that is exactly what i need. This means its O(n^2) –  Luke McGregor Apr 29 '12 at 3:50

Since $$\sum_{i=0}^N(N-i)=\sum_{i=0}^Ni=\frac{N(N+1)}2\;,$$ this is just the sum of the first $N$ positive integers, which is sometimes called the $N$-th triangular number. It’s also the binomial coefficient $\dbinom{N+1}2$.

share|improve this answer

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.