1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.