Question

Prove that an = 4^n + 2(-1)^nis the solution to

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

Answer 1

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.