32.5k views
0 votes
Prove that an = 4^n + 2(-1)^nis the solution to

therecurrence relation an = 3an-1
+4an-2 for n>=2.

User Jiriki
by
7.7k points

1 Answer

5 votes

Answer:

See proof below

Explanation:

We have to verify that if we substitute
a_n=4^n+2(-1)^n in the equation
a_n=3a_(n-1)+4a_(n-2) the equality is true.

Let's substitute first in the right hand side:


3a_(n-1)+4a_(n-2)=3(4^(n-1)+2(-1)^(n-1))+4(4^(n-2)+2(-1)^(n-2))

Now we use the distributive laws. Also, note that
(-1)^(n-1)=(1)/(-1)(-1)^n=(-1)(-1)^(n) (this also works when the power is n-2).


=3(4^(n-1))+6(-1)^(n-1)+4(4^(n-2))+8(-1)^(n-2)


=3(4^(n-1))+(-1)(6)(-1)^(n)+4^(n-1)+(-1)^2(8)(-1)^(n)


=4(4^(n-1))-6(-1)^(n)+8(-1)^(n)=4^n+2(-1)^n=a_n

then the sequence solves the recurrence relation.

User Andrew McGivery
by
7.9k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.