Solve the recurrence relation $a_n=4a_{n-1}-3a_{n-2}+2^n$ with $a_1=1, a_2=11$

Question

Solve the recurrence relation: $$a_n=4a_{n-1}-3a_{n-2}+2^n$$ With initial conditions: $$a_1=1, a_2=11$$ I know that this is a non-homogeneous recurrence relation meaning that the first step is to solve the homogeneous part: $$r^n=4r^{n-1}-3^r{n-2}$$ $$r^2=4r-3$$ $$r^2-4r+3=0$$ $$(r-1)(r-3)=0$$ $$r=1,r=3$$ This gives us: $$a_n=A(1)^n+B(3)^n$$ or (if the constant B absorbs A) $$a_n=B(3)^n$$ The non-homogeneous part is where I seem to get stuck. I attempted: $$a_n=B(3)^n+C(2)^n$$ subbing it into the original recurrence relation: $$B(3)^n+C(2)^n= 4[B(3)^{n-1}+C(2)^{n-1}]-3[B(3)^{n-2}+C(2)^{n-2}]+2^n$$ I am a lost on where to proceed from here. Any help would be appreciated!

Answer 1

Let us look for a solution of shape $c2^n$ of the non-homogeneous equation. Substituting we get $$c2^n=4c2^{n-1}-3c2^{n-2}+2^n.$$ Dividing by $2^{n-2}$ we get $4c=8c-3c+4$, and now we know $c$.

Finally, we can write down the general solution of the non-homogeneous equation, and then meet the initial conditions.

Answer 2

For the non-homogeneous part of $a_n=4a_{n-1}-3a_{n-2}+2^n $, I'll try $a_n = c 2^n$.

Then $c2^n=4c2^{n-1}-3c2^{n-2}+2^n $ or, dividing by $2^{n-2}$, $4c =8c-3c+4$ or $c=-4$.

As a check, if $a^n = -4\,2^n =-2^{n+2} $,

$\begin{array}\\ 4a_{n-1}-3a_{n-2}+2^n &=-4\,2^{n+1}+3\, 2^n+2^n\\ &=2^n(-8+3+1)\\ &=-4\,2^n\\ &=a_n\\ \end{array} $

As to how I chose this form to try, experience.

Answer 3

Let $$ b_n=a_n+2^{n+2} \quad \forall n\ge 1. $$ Then $$ b_1=a_1+2^3=9,\quad b_2=a_2+2^4=27, $$ and for every $n\ge 3$ we have: \begin{eqnarray} b_n&=&4(b_{n-1}-2^{n+1})-3(b_{n-2}-2^n)+2^{n+2}+2^n\\ &=&4b_{n-1}-3b_{n-2}+(-8+3+4+1)2^n\\ &=&4b_{n-1}-3b_{n-2}. \end{eqnarray} The characteristic equation associated to the recurrence relation $$ b_n-4b_{n-1}+3b_{n-2}=0 $$ is $$ r^2-4r+3=0, $$ and its solutions are $$ r_1=1, \quad r_2=3. $$ Therefore $$ b_n=c_1+c_2\cdot3^n, $$ where $c_1$ and $c_2$ satisfy: $$ c_1+3c_2=9,\quad c_1+9c_2=27, $$ i.e. $$ c_1=0,\quad c_2=3. $$ Hence $$ a_n=b_n-2^{n+2}=3^{n+1}-2^{n+2} $$