Question

Find the solution of the recurrence relation ${\mathit{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}}\mathbf{+}\mathbf{1}$if${\mathit{a}}_{\mathbf{0}}\mathbf{=}\mathbf{2}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{=}\mathbf{4}$and${\mathit{a}}_{\mathbf{2}}\mathbf{=}\mathbf{8}$

Short answer

The solution is

$\begin{array}{l}{a}_n={\alpha }_1+{\alpha }_{2}n+{\alpha }_3{n}^2+\frac{1}{6}{n}^3\\ =2+\frac{4n}{3}+\frac{n^2}{2}+\frac{n^3}{6}\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}+1\\ a_0=2\\ a_1=4\\ a_2=8\\ \end{array}$

Definition

The equation is said to be linear homogeneous difference equation if and only if $\mathit{R}\left(n\right)\mathbf{=}\mathbf{0}$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}+1\\ a_0=2\\ a_1=4\\ a_2=8\\ \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& \text{Characteristic}\text{equation}\\ r^3-3r^2+3r-1& =0& \\ {(r-1)}^3& =\frac{3\pm \sqrt{{(-3)}^2-4\left(1\right)(-2)}}{2}& {(a-b)}^3=a^3-3a^{2}b+3a{b}^2+b^3\\ r-1& =0& \text{Zero}\text{product}\text{property}\\ r& =0\text{with}\text{multiplicity}3& \\ & & \end{array}$

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\\ F\left(n\right)=1=1·1^n\end{array}$

If $F\left(n\right)=\left(b_t{n}^t+b_{t-1}{n}^{t-1}+\dots +b_{1}n+b_0\right)s^n$and $s$is$a$root of the characteristic equation with multiplicity $m$then$n^m\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_1\right.$the particular solution.

$a_n^{\left(p\right)}=p_0·n^3·1^n=p_0{n}^3$

The particular solution needs to satisfy the recurrence relation:

$\begin{array}{cc}{a}_n& =3a_{n-1}-3a_{n-2}+a_{n-3}+1\\ p_0{n}^3& =3p_0{(n-1)}^3-3p_0{(n-2)}^3+p_0{(n-3)}^3+1\\ & {(a-b)}^3=a^3-3a^{2}b+a{b}^2-b^3\\ & \end{array}$

$p_0{n}^3=3p_0\left(n^3-3n^2+3n-1\right)-3p_0\left(n^3-6n^2+12n-8\right)+p_0\left(n^3-9n^2+27n-27\right)+1$

Combine like terms

$\begin{array}{cc}0& =-6p_0+1\\ -1& =-6p_0\\ \frac{1}{6}& =p_0\\ & \end{array}$

Thus, the particular solution then becomes:

$a_n^{\left(p\right)}=p_0{n}^3=\frac{1}{6}{n}^3$

SOLUTION NON-HOMOGENEOUS RECURRENCE RELATION

The solution of the non-homogeneous recurrence relation is the sum of the solution of the homogeneous recurrence relation and the lution:

$a_n=a_n^{\left(h\right)}+a_n^{\left(h\right)}={\alpha }_1+{\alpha }_{2}n+{\alpha }_3{n}^2+\frac{1}{6}{n}^3$

Use initial conditions:

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

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

$\begin{array}{cc}& 4=2+{\alpha }_2+{\alpha }_3+\frac{1}{6}\\ & 8=2+2{\alpha }_3+4{\alpha }_3+\frac{4}{3}\\ & \end{array}$

Subtract$\frac{13}{6}$from each side of the first equation

Subtract $\frac{10}{3}$from each side of the second equation

$\begin{array}{cc}& \frac{11}{6}={\alpha }_2+{\alpha }_3\\ & \frac{14}{3}=2{\alpha }_3+4{\alpha }_3\\ & \end{array}$

Multiply the first equation by 2

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

Subtract the two equations

$\begin{array}{c}1=2{\alpha }_3\\ \frac{1}{2}={\alpha }_3\\ \end{array}$

Determine ${\alpha }_2$

$\begin{array}{l}{\alpha }_2=\frac{11}{6}-{\alpha }_3\\ =\frac{11}{6}-\frac{1}{2}=\frac{4}{3}\end{array}$

Hence, the solution is

$\begin{array}{l}{a}_n={\alpha }_1+{\alpha }_{2}n+{\alpha }_3{n}^2+\frac{1}{6}{n}^3\\ =2+\frac{4n}{3}+\frac{n^2}{2}+\frac{n^3}{6}\end{array}$