|
Size: 1190
Comment:
|
← Revision 17 as of 2020-01-26 21:02:57 ⇥
Size: 1562
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Summing a finitite series of natural numbers = | = Summing a finite series of natural numbers = |
| Line 3: | Line 3: |
| Really we'll only treat the case starting with 1. Given a sequence of numbers <<latex(1, 2, 3, \ldots , N)>>, the series is given by <<latex(1+2+3+\ldots+N)>>. Finding the sum of the series is actually quite simple: | Back to PrinciplesOfNetworkingCourse |
| Line 5: | Line 5: |
| {{{#!latex | 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: |
| Line 8: | Line 8: |
| \[ \sum_{i=1}^{N}i = 1+2+3+\ldots+N \] |
$$$\sum_{i=1}^{N}i = 1+2+3+\ldots+N$$$ |
| Line 12: | Line 12: |
| \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: \[ \sum_{i=1}^{N} i = \frac{N(N+1)}{2} \] What 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} |
$$$\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}$$$ |
| Line 27: | Line 24: |
| }}} | 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$$? |
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$$?