Solving Linear Recurrence Relations

Distinct Roots

Let $c_1,c_2,\dots ,c_k$ be real numbers. Suppose that the characteristic equation

$$r^k-c_1{r}^{k-1}-\cdots -c_k=0$$

has $k$ distinct roots $r_1,r_2,\dots ,r_k$. Then a sequence $\left\{a_n\right\}$ is a solution of the recurrence relation

$$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}$$

if and only if

$$a_n={\alpha }_1{r}_1^n+{\alpha }_2{r}_2^n+\cdots +{\alpha }_k{r}_k^n$$

for $n=0,1,2,\dots$, where ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ are constants that can be derived from initial conditions.

General Case

Let $c_1,c_2,\dots ,c_k$ be real numbers. Suppose that the characteristic equation

$$r^k-c_1{r}^{k-1}-\cdots -c_k=0$$

has $t$ distinct roots $r_1,r_2,\dots ,r_t$ with multiplicities $m_1,m_2,\dots ,m_t$, respectively, so that $m_i\ge 1$ for $i=1,2,\dots ,t$ and $m_1+m_2+\cdots +m_t=k$. Then a sequence $\left\{a_n\right\}$ is a solution of the recurrence relation

$$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}$$

if and only if

$$\begin{array}{rl}{a}_n& =({\alpha }_{1,0}+{\alpha }_{1,1}n+\cdots +{\alpha }_{1,m_1-1}{n}^{m_1-1})r_1^n\\ & +({\alpha }_{2,0}+{\alpha }_{2,1}n+\cdots +{\alpha }_{2,m_2-1}{n}^{m_2-1})r_2^n\\ & +\cdots +({\alpha }_{t,0}+{\alpha }_{t,1}n+\cdots +{\alpha }_{t,m_t-1}{n}^{m_t-1})r_t^n\end{array}$$

for $n=0,1,2,\dots$, where ${\alpha }_{i,j}$ are constants for $1\le i\le t$ and $0\le j\le m_i-1$ that can be derived from initial conditions.

Non-homogenous Case

If $\left\{a_n^p\right\}$ is a particular solution of the non-homogeneous linear recurrence relation with constant coefficients

$$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}+F(n)$$

then every solution is of the form $\left\{a_n^{(p)}+a_n^{(h)}\right\}$, where $\left\{a_n^{(h)}\right\}$ is a solution of the associated homogeneous recurrence relation

$$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}$$