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