|
Size: 1659
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 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: |
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 10: | Line 8: |
| \begin{equation} \sum_{i=1}^{N}i = 1+2+3+\ldots+N \end{equation} |
$$$\sum_{i=1}^{N}i = 1+2+3+\ldots+N$$$ |
| Line 14: | 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: \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} |
$$$\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 30: | Line 25: |
| 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$? }}} |
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$$?