# Solve the recurrence relation $a_{k+2}-6a_{k+1}+9a_k=3(2^k)+7(3^k), k\geq 0, k_0=1,k_1=4.$

Solve the recurrence relation $a_{k+2}-6a_{k+1}+9a_k=3(2^k)+7(3^k), k\geq 0, k_0=1,k_1=4.$

I know that I need a general solution of the form $a_k=a^{(h)}_k+a^{(p)}_k$, where the first term is a general solution to the recurrence relation given on the LHS and the particular solution which depends on both the LHS and the RHS.

So far, I got the characteristic polynomial of the LHS, which is given by $t^2-6t+9=(t-3)^2=0.$ So I have double roots $t=3$. So the homogenous solution is given by $a^{(h)}_k=x3^k+ky3^k$.

Now i'm having trouble determining the particular solution. How do I proceed?

• – Lucian Feb 26 '16 at 16:47

The $3(2^k)$ part is easy to deal with. Look for a solution of the shape $c(2^k)$.
The $7(3^k)$ part is made more complicated by the fact that $3$ is a root, indeed a double root, of the characteristic polynomial. Look for a solution of the shape $dk^2(3^k)$. There will be very nice cancellation.
• Thanks, I can't seem to understand why we should look for a solution of the shape $dk^2(3^k)$ given that $3$ is a double root. – user265675 Feb 26 '16 at 2:31
• You are welcome. Complicated to explain, just as it is complicated to explain why we should look for a solution of the homogeneous equation of the shape $x(3^k)+yk(3^k)$. But try it, you will like it. – André Nicolas Feb 26 '16 at 2:38