Question

Find the solution of the recurrence relation $a_{\mathbf{n}}\mathbf{=}\mathbf{3}{\mathit{a}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{-}\mathbf{3}{\mathit{a}}_{\mathbf{n}\mathbf{-}\mathbf{2}}\mathbf{+}{\mathit{a}}_{\mathbf{n}\mathbf{-}\mathbf{3}}$if ${\mathit{a}}_{\mathbf{0}}\mathbf{=}\mathbf{2}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{=}\mathbf{2}$, and${\mathit{a}}_{\mathbf{2}}\mathbf{=}\mathbf{4}\mathbf{.}$

Short answer

The solution is

$\begin{array}{l}{a}_n={\alpha }_1+{\alpha }_{2}n+{\alpha }_3{n}^2\\ =2-n+n^2\end{array}$

Step-by-step solution

Given data

We have given,

$\begin{array}{c}{a}_n=3a_{n-1}-3a_{n-2}+a_{n-3}\\ a_0=2\\ a_1=2\\ a_2=4\\ \end{array}$

Definition

The equation is said to be linear homogeneous difference equation if and only $\mathit{R}\left(n\right)\mathbf{=}\mathbf{0}$if and it will be of order n.

The equation is said to be linear non-homogeneous difference equation if $\mathit{R}\left(n\right)\mathbf{\ne }\mathbf{0}$

SOLUTION HOMOGENEOUS RECURRENCE RELATION

Given:

$\begin{array}{c}{a}_n=3a_{n-1}-3a_{n-2}+a_{n-3}\\ a_0=2\\ a_1=2\\ a_2=4\\ \end{array}$

Let,

$\begin{array}{l}{a}_n=r^3,\\ a_{n-1}=r^2,\\ a_{n-2}=r\\ a_{n-3}=1\end{array}$(Let any other terms be zero)

$\begin{array}{ccc}{r}^3& =3r^2-3r+1& \\ r^3-3r^2+3r-1& =0& \\ {(r-1)}^3& & =\frac{3\pm \sqrt{{(-3)}^2-4\left(1\right)(-2)}}{2}\\ r-1& =0& \\ r& =0\text{with}\text{multiplicity}3& \\ & & \end{array}$

SOLUTION NON-HOMOGENEOUS RECURRENCE RELATION

The solution of the recurrence relation is of the form $a_n={\alpha }_1{r}_1^n+{\alpha }_{2}n{r}_1^n+\dots +{\alpha }_k{n}^{k-1}{r}_1^n$with $r_{1}a$root with multiplicity $k$of the characteristic equation.

$\begin{array}{l}{a}_n^{\left(h\right)}={\alpha }_1·1^n+{\alpha }_2·n·1^n+{\alpha }_3·n^2·1^n\\ ={\alpha }_1+{\alpha }_{2}n+{\alpha }_3{n}^2\end{array}$

Use initial conditions:

$\begin{array}{cc}& 2=a_0={\alpha }_1\\ & 2=a_1={\alpha }_1+{\alpha }_2+{\alpha }_3\\ & 4=a_2={\alpha }_1+2{\alpha }_3+4{\alpha }_3\\ & \end{array}$

Use ${\alpha }_1=2$the other equations

$\begin{array}{cc}& 2=2+{\alpha }_2+{\alpha }_3\\ & 4=2+2{\alpha }_3+4{\alpha }_3\\ & \end{array}$

Subtract 2 from each side of each equation

$\begin{array}{cc}& 0={\alpha }_2+{\alpha }_3\\ & 2=2{\alpha }_3+4{\alpha }_3\\ & \end{array}$

Multiply the first equation by 2

$\begin{array}{cc}& 0=2{\alpha }_2+2{\alpha }_3\\ & 2=2{\alpha }_3+4{\alpha }_3\\ & \end{array}$

Subtract the two equations

$\begin{array}{cc}& 2=2{\alpha }_3\\ & 1={\alpha }_3\\ & \end{array}$

Determine ${\alpha }_2,$

${\alpha }_2=-{\alpha }_3=-1$

Hence, the solution is

$\begin{array}{l}{a}_n={\alpha }_1+{\alpha }_{2}n+{\alpha }_3{n}^2\\ =2-n+n^2\end{array}$