# Name of function: $\sum_{i=0}^N(N-i)$

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.

-
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
Arithmetic progression. – David Mitra Apr 29 '12 at 3:41

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.

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

-