# Sequences

- A sequence is an ordered list of values.
- e.g. the sequence of powers of two: \(1,2,4,8,16,32,64,\ldots\).
- e.g. the sequence of digits: \(0,1,2,3,4,5,6,7,8,9\).
- We can think of a sequence as a function mapping the natural numbers (\(\{0,1,2,3,\ldots\}\) or some subset) to the values in the sequence.
- e.g. \(f(n)=2^{n-1}\)
- Usually when thinking of it as a sequence, we will label the elements \(a_n\), so would write \(a_n=2^{n-1}\) instead.

- We can start the sequence with either \(n=0\) or \(n=1\).
- Whichever is more convenient.
- Or could start anywhere else if we needed to.
- So, would probably have written the above as \(a_n=2^n\).

- An arithmetic progression is a sequence where each term differs by a real number:
\[a,a+d,a+2d,a+3d,\ldots\,.\]
- So, term \(n\) is \(a_n=a+dn\).

- An geometric progression is a sequence where each term is multiplied by a constant factor:
\[a,ar,ar^2,ar^3,\ldots\,.\]
- So, term \(n\) is \(a_n=ar^n\).
- The powers of two above were a geometric progression with \(a=1\) and \(r=2\).

# Summations

- A summation is what you get when you add up a sequence.
- For a sequence with terms up to \(a_n\), its summation is \(a_0+a_1+\cdots +a_n\).
- This is usually written (for finite and infinite sequences) \[\sum_{i=0}^{n} a_i \qquad \sum_{i=0}^{\infty} a_i\,.\]

*Theorem:*For real numbers \(a\) and \(r\), with \(r\) not 0 or 1, \[\sum_{i=0}^{n} ar^i = a\frac{r^{n+1}-1}{r-1}\,.\]*Proof:*Let \(S=\sum_{i=0}^{n} ar^i\). Then, \[\begin{align*} rS &= r\sum_{i=0}^{n} ar^i \\ &= \sum_{i=0}^{n} ar^{i+1} \\ &= \sum_{j=1}^{n+1} ar^{j} \\ &= \left[\sum_{j=0}^{n} ar^{j}\right] + ar^{n+1} - a \\ &= S + ar^{n+1} - a \,. \end{align*}\] Now we can simplify the equation to \[\begin{align*} rS &= S + ar^{n+1} - a \\ (r-1)S &= a(r^{n+1} - 1) \\ S &= a\frac{r^{n+1} - 1}{r-1}\,.\quad ∎ \end{align*}\]- We will have more use for summation as the course goes on… let's get those details as we need them.