|
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
Given the series:
We can rearrange the series like so:
The question is where does it stop? That is, how many
But what if its odd? Well, the middle term will now be
So we see that this series always converges to the same formula.
In the above case, we have seen that