# Recurrence relation (linear, second-order, constant coefficients)

Q1. Find the general solution to the difference equation

$$a_{n} - 4a_{n-1} + 3a_{n-2} = 6$$

Q2. Solve the difference equation

$$a_{n} - a_{n-1} - 2a_{n-2} = 0, a_0 = 2, a_1 = 4$$

I am completely lost in solving recurrence relation questions. Can anyone guide me in steps to solve the following 2 questions?

-
Re Q2, you could try to compute the first terms, to see if a pattern emerges. – Did May 5 '11 at 10:08
Don't you have a guide for that in your textbooks? Those are pretty standard. – Raskolnikov May 5 '11 at 10:10
@Raskolnikov I dont understand the examples on the textbook. – optimus May 5 '11 at 10:13
For linear recurrence relations, one can get some insight but making the ansatz $a_n = \lambda^n$ and then figuring out which $\lambda$s fulfill the equation (then one can take an arbitrary linear combination of these solutions in order to get the initial conditions right). – Fabian May 5 '11 at 10:13

The general approach to solving recurrence relations is the following: given a recurrence relation $$a_n+\alpha_1a_{n-1}+...+\alpha_ra_{n-r}=\beta(n) \; .$$

I) First you solve the homogeneous part $a_n^{(h)}+\alpha_1a_{n-1}^{(h)}+...+\alpha_ra_{n-r}^{(h)}=0$:
$\quad$ a) By solving the characteristic equation: $x^r+\alpha_1x^{r-1}+...+\alpha_r=0$ you get $x_1,...,x_r$ the roots of the equation.
$\quad$ b) If all $x_1,...,x_r$ are different then the $a_n^{(h)}=A_1x_1^n+...+A_rx_r^n$, where $A_1,...,A_r$ are the coefficients.
$\quad$ c) If you have a root $x_j$ is of multiplicity $k$ then you replace the term $A_jx_j^n$ with $(B_1n^{k-1}+...+B_k)x_j^n$

II) Now you find a particular solution to the equation $a_n^{(p)}+\alpha_1a_{n-1}^{(p)}+...+\alpha_ra_{n-r}^{(p)}=\beta(n)$. Each $\beta(n)$ needs a different approch to guess $a_n^{(p)}$. For example, if $\beta(n)=k^nf(n)$, where $k$ is a number and $f(n)$ is a polynomial in $n$, then $a_n^{(p)}=k^nn^sg(n)$ where $k$ is the same $k$, $s$ is the multiplicity of $k$ as a root of the characteristic equation in the homogeneous part and $g(n)$ is a polynomial of the same degree as $f(n)$.

Finally, $a_n=a_n^{(h)}+a_n^{(p)}$

-
 can you explain the purpose of finding general solution and particular solutions for linear difference equation? – optimus May 5 '11 at 11:01 @liang The purpose is that you find a general solution for a simpler equation and a particular solution for the complicated equation to arrive at the general solution for the complicated equation. – Phira May 5 '11 at 11:17 @liangteh: In addition to what user9325 said, you can check that the set of all sequences $a_n$ that obey to a homogeneous recurrence relation form a vector space over $\mathbb{C}$. Hence, the set of all solutions of a non-homogeneous recurrence relation forms an affine vector space. – Dennis Gulko May 5 '11 at 11:32

The general second order homogeneous linear recurrence/difference equation with constant coefficients

$$x_{n}+c_{1}x_{n-1}+c_{2}x_{n-2}=0\qquad (1)$$

has two fundamental solutions $(\lambda _{1}^{n})_{n\geq 0}$ and $(\lambda _{2}^{n})_{n\geq 0}$, where $\lambda _{1},\lambda _{2}$ are the two zeroes of the characteristic polynomial

$$\lambda ^{2}+c_{1}\lambda +c_{2}\qquad (2)$$

Let's confirm.

$$\begin{eqnarray*} \lambda _{1}^{n}+c_{1}\lambda _{1}^{n-1}+c_{2}\lambda _{1}^{n-2} &=&\lambda _{1}^{n-2}\left( \lambda _{1}^{2}+c_{1}\lambda _{1}+c_{2}\right) \equiv 0 \\ && \\ \lambda _{2}^{n}+c_{1}\lambda _{2}^{n-1}+c_{2}\lambda _{2}^{n-2} &=&\lambda _{2}^{n-2}\left( \lambda _{2}^{2}+c_{2}\lambda _{2}+c_{2}\right) \equiv 0 \end{eqnarray*}$$

If $\lambda _{1}\neq \lambda _{2}$ the general solution of $(1)$ is a linear combination of $\lambda _{1}^{n}$ and $\lambda _{2}^{n}$

$$x_{n}=A\lambda _{1}^{n}+B\lambda _{2}^{n}\qquad (3)$$

as you can confirm substituting $(3)$ in $(1)$. Let's apply this result to your second difference equation $a_{n}-a_{n-1}-2a_{n-2}=0$. The characteristic polynomial $\lambda ^{2}-\lambda -2$ has the zeroes $\lambda _{1}=-1,\lambda _{2}=2$.

Thus $(3)$ becomes

$$a_{n}=A(-1)^{n}+B2^{n}$$

The constants $A$ and $B$ are determined by using the initial conditions $a_{0}=2$, $a_{1}=4$.

Added: Determination of $A$ and $B$:

$$a_{0}=A(-1)^{0}+B2^{0}=A+B=2\Leftrightarrow B=2-A$$

Hence

$$a_{n}=A(-1)^{n}+\left( 2-A\right) 2^{n}$$

and

$$a_{1}=A(-1)^{1}+\left( 2-A\right) 2^{1}=-A+4-2A=-3A+4=4\Leftrightarrow A=0.$$

Since $A=0$ and $B=2-A=2$ the solution is

$$a_{n}=2\cdot 2^{n}=2^{n+1}\qquad n\geq 2$$

As for your first equation it is not homogenous because the RHS is not zero. For solving it, please see the explanation by Dennis Gulko in his answer.

-
 @Américo Tavares: why one gets a cubic characteristic polynomial for the first equation? – Fabian May 5 '11 at 11:56 @Fabian: It was my big mistake. I will correct it. Many thanks! – Américo Tavares May 5 '11 at 11:58 my try at Q2 after the explanations. Please pardon the mistake if there are any. characteristic equation: $$x^2 - x - x = 0$$ $$(x+1)(x-2) = 0$$ $$x = -1, 2$$ General solution $$A_n = A_1(-1)^n + A_2(2)^n$$ Now $$a_0 = 2, a_1 = 4$$ $$a_0 = A_1 (-1)^0 + A_2(2)^0$$ $$A_1 + A_2 = 2$$ $$A_1 = A_1(-1)^1 + A_2(2)^1$$ $$4+2 = -K_1 + 2K_2 + K_1 + K_2$$ $$6 = 3K_2$$ So $$K_1 = 0, K_2 = 2$$ Hence $$A_n = 0(-1)^n + 2(2)^n$$ $$A_n = 2(2)^n$$ Please pardon if there any mistakes – optimus May 5 '11 at 12:12 The independant term is -2. The characteristic equation is $x^2-x-2=0$, which is equivalent to $(x+1)(x-2)=0$. I used the variable $\lambda$ instead. – Américo Tavares May 5 '11 at 12:15 @Américo Tavares: Noted. Your explanation is quite similar to the textbook examples. – optimus May 5 '11 at 12:24