Summations
Table of Contents
1. Summations
1.1. Types of Summations
- Geometric Sequence
- The is a sequence that has something the power of \(i\).
1.2. Useful Summation Formulas
1.2.1. Arithmetic Sum
\(\sum\limits_{i = 1}^{n} i = \frac{n ( n + 1 )}{2}\)
1.2.2. Sum of Squares
\(\sum\limits_{i = 1}^{n} i^2 = \frac{n ( n+ 1 )( 2n + 1 )}{6}\)
1.2.3. Sum of Cubes
\(\sum\limits_{i = 1}^{n}i ^3 = \frac{n^2 (n + 1)^2}{4}\)
1.2.4. Finite Geometric Sum
\(\sum\limits_{i = 0}^{n} r^i = \frac{r^{n + 1} - 1}{r - 1}\)
1.2.5. Infinite Geometric Series
\(\sum\limits_{i = 0}^{\infty} r^i = \frac{1}{1 - r}\) when \(|r| < 1\)
2. Analysing Summations
Using the properties of summations, we want to make a summation look like something that we can more easily analyze.
2.1. Example
\begin{align}
\sum\limits_{i = 1}^{n} (2i^2 + 3i + 5) & = 2 \sum\limits_{i = 1}^{n} i^2 + 3 \sum\limits_{i = 1}^{n} i + \sum\limits_{i=1}^{n} 5 \\
& = 2 \left[ \frac{n ( n+1 ) (2n + 1)}{6} \right] + 3 \left[ \frac{n (n+1)}{2} \right] + 5n
\end{align}
2.2. Complexity Of Summations
The whole reason we are looking at summations is because we want to determine their asymtotical complexity.