Overview

A sequence is an ordered list of numbers. These are usually represented as a closed formula or a recursive definition.

Recurrence Relations

To solve a recurrence relation means to find a closed form for the relation (with respect to initial conditions).

Telescoping

Telescoping refers to the property of summations in which consecutive terms cancel out. We can use telescoping to solve recurrences of form $a_n=a_{n-1}+f(n)$ by noticing that: \begin{align*} a_1 - a_0 & = f(1) \\ a_2 - a_1 & = f(2) \\ \vdots \\ a_n - a_{n-1} & = f(n) \\ \hline a_n - a_0 & = \sum_{k=1}^n f(n) \end{align*}

Iteration

Iteration refers to the expansion of terms, starting at the initial conditions, in the hope of discovering a pattern. It is more general than Telescoping is. Consider $a_n=a_{n-1}+f(n)$ again. We solve with iteration like so: \begin{align*} a_1 & = a_0 + f(1) \\ a_2 & = (a_0 + f(1)) + f(2) \\ \vdots \\ a_n & = (\cdots(a_0 + f(1)) + f(2)) + \cdots) + f(n) \\ \hline a_n & = a_0 + \sum_{k=1}^n f(n) \end{align*}

Characteristic Roots

When encountering linear homogeneous recurrence relations with constant coefficients, we can use the characteristic root technique to solve. We demonstrate with a quadratic characteristic polynomial, though this technique generalizes to higher-order polynomials as well.

Given recurrence relation $a_n+\alpha a_{n-1}+\beta a_{n-2}=0$, the characteristic polynomial is $r^2+\alpha r+\beta$. If $r_1$ and $r_2$ are distinct roots of the characteristic polynomial, then the solution to the recurrence relation is $a_n=a{r}_1^n+b{r}_2^n$ where $a$ and $b$ are determined by the initial conditions. If the characteristic polynomial only has one root $r$, the solution is instead $a_n=a{r}^n+bn{r}^n$

Bibliography

• Oscar Levin, Discrete Mathematics: An Open Introduction, 3rd ed., n.d., https://discrete.openmathbooks.org/pdfs/dmoi3-tablet.pdf.
• Ronald L. Graham, Donald Ervin Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed (Reading, Mass: Addison-Wesley, 1994).