function of input size N, combination problem Can someone please elaborate how from $(N+1)+N+(N-1)+(N-2)$ one can get $= 
1/2(N+1)(N+2)$?
also how to prove that: $(N-1)+(N-2)+...+3+2+1+0 = \frac{N(N-1)}{2} = {N \choose 2}$ ?
Thank you!
 A: This might help give you an intuitive idea of why those quantities are related:
Say you have a set of $N$ things, and you're going to pick $2$ of them, where order doesn't matter.  Give each thing a number from $1$ to $N$, and put them in order from thing $N$ down to thing $1$, like so:
$$ N,N-1,N-2,...,2,1 $$
Now, we can pick the first thing that will be in our set of $2$.  We can pick thing $N$ as the first thing.  Let's mark the thing we chose by coloring it red:
$$ \color{red}{N},N-1,N-2,...,2,1 $$
Next, we can choose any of the other things as the second thing in our set of two.  We have $N-1$ options for choosing the second thing, and each of them gives us one possible set of $2$ chosen from our original set.  Let's color the second things blue.  These look like:
$$ \color{red}{N},\color{blue}{N-1},N-2,...,2,1 $$
$$ \color{red}{N},N-1,\color{blue}{N-2},...,2,1 $$
$$ \color{red}{N},N-1,N-2,...,\color{blue}{2},1 $$
$$ \color{red}{N},N-1,N-2,...,2,\color{blue}{1} $$
After coloring thing $N$ red, we have $N-1$ choices of things to color blue.
Now, let's select thing $N-1$ first, color it red, and then pick a second thing to color blue.  We get this:  
$$ \color{blue}{N},\color{red}{N-1},N-2,...,2,1 $$
$$ N,\color{red}{N-1},\color{blue}{N-2},...,2,1 $$
$$ N,\color{red}{N-1},N-2,...,\color{blue}{2},1 $$
$$ N,\color{red}{N-1},N-2,...,2,\color{blue}{1} $$
After coloring thing $N-1$ red, we can choose any of the other $N-1$ things to color blue.  
In general, after coloring one of $N$ things red, we have $N-1$ choices for the thing to color blue.  We have a total of $N(N-1)$ choices for how to color one thing red and one thing blue.  
We can relate this to ${N \choose 2}$, the number of ways to choose $2$ things out of $N$.  After we painted one thing red and one thing blue above, there are exactly two painted things.  Take those two to be the $2$ chosen things out of the $N$ things.  However, we've effectively chosen each pair of things twice: once where the first is red and the second is blue, and again where the first is blue and the second is red.  We double counted each possibility, so ${N \choose 2}$ is actually equal to $\frac{N(N-1)}{2}$.
We can see how this is related to $(N-1)+(N-2)+...+2+1+0$ by thinking about the number of ways to color two things red, instead of coloring one red and one blue.  We can choose to color thing $N$ red first:
$$ \color{red}{N},N-1,N-2,...,2,1 $$
and then color any of the other $N-1$ things red second:
$$ \color{red}{N},\color{red}{N-1},N-2,...,2,1 $$
$$ N,\color{red}{N-1},\color{red}{N-2},...,2,1 $$
$$ N,\color{red}{N-1},N-2,...,\color{red}{2},1 $$
$$ N,\color{red}{N-1},N-2,...,2,\color{red}{1} $$
After coloring thing $N$ red, we had $N-1$ choices for the other thing to color.
Now, let's color thing $N-1$ red first:
$$ N,\color{red}{N-1},N-2,...,2,1 $$
We have $N-1$ choices for the second thing to color red, but if we pick thing $N$, we end up with:
$$ \color{red}{N},\color{red}{N-1},N-2,...,2,1 $$
which we already counted when we were painting thing $N$ first.  So there are $N-2$ things we can paint red and end up with a new pair of red things:
$$ N,\color{red}{N-1},\color{red}{N-2},...,2,1 $$
$$ N,\color{red}{N-1},N-2,...,\color{red}{2},1 $$
$$ N,\color{red}{N-1},N-2,...,2,\color{red}{1} $$
There are $N-2$ new pairs of red things we can get by painting thing $N-1$ first.  If we paint thing $N-2$ first, there are $N-3$ new pairs, since we already counted the pairs $(N,N-2)$ and $(N-1,N-2)$.  If we paint thing $N-3$ first, there are $N-4$ new pairs, and so on.  
This continues to the point where we paint thing $1$ first.  There are no new pairs of two red things we can create by painting thing $1$ first, since thing $1$ was painted red along with each other thing when we were painting those other things first.
So ${N \choose 2}$, the total number of ways we can pick $2$ things from $N$ things, is the total number of ways we can pick thing $N$ first, plus the total number of ways we can pick thing $N-1$ first without picking any of the same combinations, and so on.  This is equal to:
$$(N-1) + (N-2) +...+2+1+0$$
Putting it all together, we have:
$$ {N \choose 2} = (N-1) + (N-2) +...+2+1+0$$
and
$$ {N \choose 2} = \frac{N(N-1)}{2}$$
so
$$ \frac{N(N-1)}{2} = (N-1) + (N-2) +...+2+1+0$$
