First-Order Linear Homogeneous Recurrence Relations

Consider the recurrence relation

$$ a_{n + 1} = da_n $$

where $n \geq 0$ and $d$ is a constant.

The general solution is

$$ a_n = Cd^n $$

for any constant $C$.

If we impose the the initial condition $a_0 = A$, then the (unique) particular solution is $a_n = Ad^n$

Note that $a_n = na_{n - 1}$ is not a first-order linear homogeneous recurrence relation. Its solution is $n!$ when $a_0 = 1$

First-Order Linear Non-homogeneous Recurrence Relations

Consider the recurrence relation

$$ a_{n + 1} + da_n = f(n) $$

where

• $n \geq 0$
• $d$ is a constant
• $f(n): \mathbb{N} \rightarrow \mathbb{R}$

A general solution no longer exists.

$k$th-Order Linear Homogeneous Recurrence Relations with Constant Coefficients

Consider

$$ C_na_n + C_{n - 1}a_{n - 1}+ ... + C_{n - k}a_{n - k} = 0 \ \ \ \ - (1) $$