Summing a finite series of natural numbers

Back to PrinciplesOfNetworkingCourse

Really we'll only treat the case starting with 1, but this can be easily extended to cover starting at some $n_0<N$. Given a sequence of numbers $1, 2, 3, \ldots , N$, the series is given by $1+2+3+\ldots+N$. Finding the sum of the series is actually quite simple:

Given the series:
\begin{equation}
     \sum_{i=1}^{N}i = 1+2+3+\ldots+N
\end{equation}
We can rearrange the series like so:
\begin{eqnarray}
     \sum_{i=1}^{N} i &=& (1+N)+(2+N-1)+\ldots \\
                      &=& (N+1) + (N+1) + \ldots
\end{eqnarray}
The question is where does it stop? That is, how many $N+1$ terms do we have? Obviously if there is an even number of elements in the sequence you can do this exactly $N/2$ times.
This gives us:
\begin{equation}
     \sum_{i=1}^{N} i = \frac{N(N+1)}{2}
\end{equation}
But what if its odd? Well, the middle term will now be $(N+1)/2$ (think about that a minute and it will be obvious to you), but you only have $N+1$ repeated $(N-1)/2$ times. That gives us the following
\begin{eqnarray}
     \sum_{i=1}^{N}i &=& \frac{(N+1)(N-1)}{2} + \frac{N+1}{2} \\
                     &=& \frac{N(N+1)}{2}
\end{eqnarray}
So we see that this series always converges to the same formula. 

In the above case, we have seen that $N$ represents the largest number in the sequence. If we are looking at a complete graph $G(V,E)$ where $N$ represents the number of nodes ($N = |V|$), the sequence goes from $1$ to $N-1$. How will this change answer?