= 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:

$$$\sum_{i=1}^{N}i = 1+2+3+\ldots+N$$$

We can rearrange the series like so:

$$$\begin{align} \sum_{i=1}^{N} i &=& (1+N)+(2+N-1)+\ldots \\ &=& (N+1) + (N+1) + \ldots \end{align}$$$

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:

$$$\sum_{i=1}^{N} i = \frac{N(N+1)}{2}$$$

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{align} \sum_{i=1}^{N}i &=& \frac{(N+1)(N-1)}{2} + \frac{N+1}{2} \\ &=& \frac{N(N+1)}{2} \end{align}$$$

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? How would it change your answer if we started at $$0$$ and went up to $$N$$?