Recurrence Relations and Mathematical Induction

Three basic types

• $a_{n+1} = a_n + d$: arithmetic, $a_n = a_1 + (n-1)d$.
• $a_{n+1} = ra_n$: geometric, $a_n = a_1r^{n-1}$.
• $a_{n+1} = a_n + f(n)$: for $n \geqq 2$, $a_n = a_1 + \sum_{k=1}^{n-1} f(k)$; check $n = 1$ at the end.

The type a(n+1) = p a(n) + q

Find $\alpha$ with $\alpha = p\alpha + q$. Then the recurrence becomes

so $\{a_n - \alpha\}$ is geometric with ratio $p$ and $a_n - \alpha = (a_1 - \alpha)p^{n-1}$.

Example: $a_1 = 3$, $a_{n+1} = 2a_n - 1$ gives $\alpha = 1$, so $a_n - 1 = 2 \cdot 2^{n-1}$ and $a_n = 2^n + 1$.

Sums and general terms

If a relation such as $S_n = 2a_n + n$ is given, subtract the same relation with $n$ replaced by $n + 1$ to get a recurrence between $a_{n+1}$ and $a_n$.

Other recurrences and induction

• $a_{n+1} = \dfrac{a_n}{pa_n + 1}$: take reciprocals; $\left\{\dfrac{1}{a_n}\right\}$ is arithmetic.
• $a_{n+1} = pa_n + q^n$: divide by $q^{n+1}$ and set $b_n = \dfrac{a_n}{q^n}$.
• $a_{n+2} = (\alpha + \beta)a_{n+1} - \alpha\beta a_n$: rewrite as $a_{n+2} - \alpha a_{n+1} = \beta(a_{n+1} - \alpha a_n)$ and the same with $\alpha, \beta$ swapped.