2
$\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 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.

$\endgroup$
3
  • $\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$ Oct 11 '15 at 22:26
  • $\begingroup$ See math.stackexchange.com/questions/1474011/… $\endgroup$
    – user236182
    Sep 28 '17 at 12:54
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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^2-4\lambda+3=0$

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

$k=-4$

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$

$1=A+3B-8$

$11=A+9B-16$

gives $10=6B-8$

$6B=18$

$B=3$

$1=A+9-8$

$A=0$

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

$\endgroup$
0
0
$\begingroup$

A general technique is to use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write your recurrence as: $$ a_{n + 2} = 4 a_{n + 1} - 3 a_n + 4 \cdot 2^n $$ Multiply by $z^n$, sum over $n \ge 0$ and recognize some sums:

$\begin{align*} \sum_{n \ge 0} a_{n + 2} z^n &= 4 \sum_{n \ge 0} a_{n + 1} z^n - 3 \sum_{n \ge 0} a_n z^n + 4 \sum_{n \ge 0} 2^n z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= 4 \frac{A(z) - a_0}{z} - 3 A(z) + 4 \frac{1}{1 - 2 z} \\ \frac{A(z) - 1 - 11 z}{z^2} &= 4 \frac{A(z) - 1}{z} - 3 A(z) + 4 \frac{1}{1 - 2 z} \end{align*}$

Solve for $A(z)$, as partial fractions:

$$ A(z) = \frac{7}{1 - 3 z} - \frac{4}{1 - 2 z} - \frac{2}{1 - z} $$

This is just geometric series. We want:

$$ a_n = [z^n] A(z) = 7 \cdot 3^n - 4 \cdot 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.