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?
Best Answer
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)}$