# Sequences and Summations

These lecture notes are mainly based on Rosen's (2011) *Discrete Mathematics and its Applications 7th Edition*.

## Sequences

A sequence is a mathematical structure that describes an ordered list of elements.

Definition from Rosen (2011)

> A **sequence** is a function from a subset of the set of integers (usually either the set $\{1,2,3,\cdots\}$) or the set $\{0,1,2,\cdots\}$ to a set $S$. We use the notation $a_n$ to denote the image of the integer $n$. We call $a_n$ a **term** of the sequence.

The shorthand $\{a_n\}$ is used to describe the sequence (ambiguous with the set containing the term $a_n$). Sequences are often described by listing the terms of the sequence in order of increasing subscripts.
$$
a_1,a_2,a_3,a_4,\cdots
$$
For example the sequence $\{a_n\}$ is a sequence where each term $a_n$:
$$
a_n=n^2
$$
Then the sequence is basically
$$
1,4,9,16,\cdots
$$

### Arithmetic Progression

An **arithmetic progression** is a special sequence that describes terms in a linear progression. It's terms follow the general form:
$$
a_n=c+dn
$$
or:
$$
c,c+d,c+2d,c+3d,c+5d,\cdots
$$
where $c$ is the **initial term** and $d$ is the **common difference**.

For example the arithmetic series where with initial term $3$ and common difference $\frac{1}{2}$ ($b_n=3+\frac{1}{2}n$) is:
$$
3,\frac{7}{2},4,\frac{9}{2},10,\cdots
$$
And another one with initial term $4$ and common difference $-1$ ($d_n=4-n$) is:
$$
4,3,2,1,0,-1,-2,\cdots
$$

### Geometric Progression

A **geometric progression** is a special sequence that describes terms in exponential progression. It's terms follow the general form:
$$
a_n=cr^n
$$
or:
$$
c,cr,cr^2,cr^3,cr^4,\cdots
$$
where, $c$ is called the **initial term** and $r$ is called the **common ratio**.

For example the geometric series where with initial term $3$ and common ratio $\frac{1}{2}$ ($b_n=3(\frac{1}{2})^n$) is :
$$
3,\frac{3}{2},\frac{3}{4},\frac{3}{8},\frac{3}{16},\cdots
$$
And another one with initial term $4$ and and common ratio $-1$ ($d_n=4(-1)^n$) is:
$$
4,-4,4,-4,4,\cdots
$$

### Recurrence Relations

> A **recurrence relation** for some sequence $\{a_n\}$ is an equation that expresses each term $a_n$ where $n\geq b$ (where $b \geq 0$) using some of the previous terms ($a_i$ where $i<n$). The sequence $\{a_n\}$ is called a **solution** for the recurrence relation it satisfies. A recursive relation **recursively defines** a sequence.

We call the terms of a recursively defined sequence $a_0,a_1,\cdots,a_b$ the **initial conditions** or the **base terms** of a recurrence relation. These terms precede the terms where the recurrence equation is applied

For example, let the sequence $\{a_n\}$ be recursively defined by the recurrence relation $a_n=2a_{n-1}$ where $n=1,2,3,4,\cdots$ and initial conditions $a_0=5$
$$
5,10,20,40,80,\cdots
$$
And the sequence $\{b_n\}$ which is recursively defined by the recurrence relation $b_n=b_{n-1}b_{n-2}$with initial conditions $b_1=1$ and $b_2=2$:
$$
1,2,2,4,8,32,265,\cdots
$$

##### Fibonacci Sequence

The Fibonacci sequence $\{f_n\}$ is a recursively defined sequence, defined as
$$
\begin{align*}
f_0&=0 \\
f_1&=1\\
f_n&=f_{n-1}+f_{n-2}
\tag{where $n$>1}
\end{align*}
$$
The sequence that satisfies these is:
$$
0,1,1,2,3,5,8,13,21,\cdots
$$

##### Factorial Sequence

The factorial sequence, commonly denoted as $a_n=n!$ can be defined using a recurrence relation:
$$
\begin{align*}
a_0&=1\\
a_n&=na_{n-1}
\end{align*}
$$
This recurrence relation defines the solution:
$$
1,1,2,6,24,120,720,5040,40320,\cdots
$$
A recurrence relation can be **solved** by finding a **closed formula** (one that does not express the each term using previous terms).

For example the recurrence relation $a_n=2a_{n-1}$ where $a_0=5$, can be solved using the closed formula describing the geometric progression $a_n=5(2^n)$.

There are two ways of solving a recurrence relation, one is by working your way up from the initial condition up to some $n^{\text{th}}$and figuring out a closed formula that provides an identical sequence:
$$
\begin{align*}
a_0&=5(2^0)=5\\
a_1&=5(2^1)=5(2)=10\\
a_2&=5(2^2)=10(2)=20\\
a_3&=5(2^3)=20(2)=40\\
&~~\vdots
\end{align*}
$$

Another is by starting from an arbitrary term of the sequence $a_n$ and solving for $a_n$ until
you reach the base terms:
$$
\begin{align*}
a_0&=5\\
a_n&=2a_{n-1}\\
a_{n-1}&=2a_{n-2}\\
a_n&=2(2a_{n-2})\\
a_{n-2}&=2a_{n-3}\\
a_n&=2(2(2a_{n-3}))\\
a_n&=2^k(a_{n-k})\\
&\tag{when $n=k$, $n-k=0$}\\
a_n&=2^n(a_{n-n})\\
a_n&=2^n(a_0)\\
a_n&=5(2^n)
\end{align*}
$$

## Summations

Given a sequence $\{a_n\}$, the sum of terms from $a_s,a_{s+1},a_{s+2},\cdots,a_{e}$ is described using the **summation notation**
$$
\sum_{i=s}^{e}{a_i}=a_i+a_{i+1}+a_{i+2}+\cdots+a_e
$$
The variable $i$ is called the **index of summation**. The variable $s$ denotes the **lower limit** of the summation. And $e$ denotes the **upper limit** of the summation

For example the value of the summation $\sum_{i=0}^{5}{i}$
$$
\sum_{i=0}^{5}{i}=0+1+2+3+4+5=15
$$
And the summation $\sum_{i=2}^{5}{i^2}$
$$
\sum_{i=2}^{6}{i^2}=4+9+16+25=54
$$

#### Some useful rules of summations

These rules are just based on rules of arithmetic

| Rule | Name |
| ------------------------------------------------------------ | -------------------- |
| $\sum_{i=s}^{e}{c}=c(e-s+1)$ | Constant summation |
| $\sum_{i=s}^{e}{a_i}+\sum_{i=s}^{e}{b_i}=\sum_{i=s}^{e}{(a_i+b_i)}$ | Combining summations |
| $\sum_{i=s}^{e}{ca_i}=c\sum_{i=s}^{e}{a_i}$ | Distributive law |
| $\sum_{i=s}^{e}{a_i}=\sum_{i=0}^{e}{a_i}-\sum_{i=0}^{s-1}{a_i}$ | Reducing bounds |

#### Sum of Arithmetic Progressions

Given an arbitrary arithmetic progression with terms $a_n=c+dn$, you can calculate the summation of its terms until the $n^{\text{th}}$ term, $\sum_{i=0}^{n}{a_i}$.

To solve this we need to make use of the arithmetic sum theorem
$$
\sum_{i=0}^{n}{i}=\frac{n(n+1)}{2}
$$
This gives the partial sum of the sequence:
$$
\begin{align*}
\sum_{i=0}^{n}{a_i}&=a_0+a_1+a_2+\cdots+a_n \\
\sum_{i=0}^{n}{a_i}&=\sum_{i=0}^{n}{(c+di)} \\
&=\sum_{i=0}^{n}{c}+\sum_{i=0}^{n}{di}\\
&=\sum_{i=0}^{n}{c}+d\sum_{i=0}^{n}{i}\\
\sum_{i=0}^{n}{a_i}&=c(n+1)+d\frac{n(n+1)}{2}
\end{align*}
$$

#### Sum of Geometric Progressions

Given an arbitrary geometric progression with terms $a_n=cr^n$, you can calculate the summation of its terms until the $n^{\text{th}}$ term, $\sum_{i=0}^{n}{a_i}$.

To solve this we need to make use of the geometric sum theorem
$$
\begin{align*}
\sum_{i=0}^{n}{r^i}&=\frac{r^{n+1}-1}{r-1} \tag{if $r\neq1$}\\
\sum_{i=0}^{n}{r^i}&=n+1 \tag{if $r=1$}\\
\end{align*}
$$
This gives the partial sum of the sequence:
$$
\begin{align*}
\sum_{i=0}^{n}{a_i}&=a_0+a_1+a_2+\cdots+a_n \\
\sum_{i=0}^{n}{a_i}&=\sum_{i=0}^{n}{cr^i} \\
\sum_{i=0}^{n}{a_i}&=c\sum_{i=0}^{n}{r^i} \\
\sum_{i=0}^{n}{a_i}&=\frac{cr^{n+1}-c}{r-1} \tag{if $r\neq1$}\\
\sum_{i=0}^{n}{a_i}&=cn+c \tag{if $r=1$}
\end{align*}
$$

#### Nested summations

Nested summations can be solved by simplifying the inner summation first and then applying it to the next
$$
\begin{align*}
\sum_{i=0}^{n}{\sum_{j=0}^{m}{ij}}&=\sum_{i=0}^{n}{(i\sum_{j=0}^{m}{j})}\\
&=\sum_{i=0}^{n}{(i\frac{m(m+1)}{2})}\\
&=\sum_{i=0}^{n}{(i\frac{m(m+1)}{2})}\\
&=\sum_{i=0}^{n}{(\frac{im^2}{2}+\frac{im}{2})}\\
&=\sum_{i=0}^{n}{(\frac{im^2}{2})}+\sum_{i=0}^{n}{(\frac{im}{2})}\\
&=\frac{m^2}{2}\sum_{i=0}^{n}{i}+\frac{m}{2}\sum_{i=0}^{n}{i}\\
&=\frac{m^2}{2}\frac{n(n+1)}{2}+\frac{m}{2}\frac{n(n+1)}{2}\\
\sum_{i=0}^{n}{\sum_{j=0}^{m}{ij}}&=\frac{n(n+1)m(m+1)}{2}
\end{align*}
$$

#### Sum of a subset notation

A summation of the form
$$
\sum_{s\in{S}}f(s)
$$
Is the sum of all $f(s)$ where $s$ is any element of $S$.

For example:
$$
\sum_{i\in\{\alpha,\beta,\gamma\}}{a_i}=a_\alpha+a_\beta+a_\gamma
$$

#### Some more useful closed form sums

**Sum of perfect squares**
$$
\sum_{i=0}^{n}{i^2}=\frac{n(n+1)(2n+1)}{6}
$$
**Sum of perfect cubes**
$$
\sum_{i=0}^{n}{i^3}=\frac{n^2(n+1)^2}{4}
$$
**Infinite sum powers**
$$
\sum_{i=1}^{\infty}{c^i}=\frac{1}{1-c} \tag{|c|<1}
$$
**Infinite sum of weighted powers**
$$
\sum_{i=1}^{\infty}{ic^{i-1}}=\frac{1}{(1-c)^2} \tag{|c|<1}
$$