|
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? |
|||||||||||
|
|
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$: 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)}$ |
|||||||
|
|
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. |
|||||||||||
|
