Solve the recurrence relation

$$a_n = 4a_{n-1} - 3a_{n-2} + 2^n $$

With initial conditions:

$a_1 = 1$

$a_2 = 11$

I have done similar recurrence relation problems to this, but none that were a non-homogeneous recurrence relation such as this one.

So far I have:

$$r^n = 4^{n-1} - 3^{n-2} $$

Divide both sides by $$\frac{1}{r^{n-2}}$$ Giving me this as my Auxiliary Equation:

$$ r^n - 4r + 3 = 0 $$

I then solved for the $r$ values and got $r = -4$ and $r = 1$ I am stumped from here as to where the non-homogeneous piece comes into play, any help is appreciated.

  • $\begingroup$ You need to find a single solution to the non-homogeneous equation. Since it contains $2^n$ part, try $c2^n$ and see if you can solve for $c$. Sidenote: double-check your solution to Auxiliary Equation. $\endgroup$ – A.S. Oct 11 '15 at 22:19
  • $\begingroup$ This question was asked and answered today. $\endgroup$ – André Nicolas Oct 11 '15 at 22:26
  • $\begingroup$ See math.stackexchange.com/questions/1474011/… $\endgroup$ – user236182 Sep 28 '17 at 12:54

Start by finding the general solution to the homogeneous recurrence relationship:

$$a_n = 4a_{n-1} - 3a_{n-2}$$

This has auxiliary equation $\lambda^2=4 \lambda-3$


$\lambda_1=1, \lambda_2=3$

$$a_n = A(1)^n +B(3)^n$$

You want a particular solution to the non-homogeneous relationship.

Try $a_n=k(2)^n$

Then $a_{n-1}=\frac 12 k(2)^n$, $a_{n-2}=\frac 14 k(2)^n$

So $k(2)^n = 4\left (\frac 12 k(2)^n \right)-3 \left(\frac 14 k(2)^n \right)+(2)^n$

$k = 2k - \frac 34 k +1$


Add this to the general solution to the homogeneous relationship to find the general solution to the non-homogeneous relationship.

$$a_n = A +B(3)^n-4(2)^n$$

Use the known values $a_1=1$ and $a_2=11$



gives $10=6B-8$





$$a_n =3(3)^n-4 (2)^n$$


Hint: $$a_n = 4a_{n-1} - 3a_{n-2} + 2^n \tag{P}$$ $$a_{n+1} = 4a_n - 3a_{n - 1} + 2^{n+1} \tag{Q}$$

Now subtract equations as $Q - 2P$.


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.