# How to solve the recurrence relation

I was going through a problem on combinatorics and came up with the recurrence relation like this. These equations hold for all natural values of $n$.

($p_n$ is the final result that I want)

$$p_n=q_n+r_n$$ $$q_{n+1}=q_n+r_n, \space r_{n+1}=2q_n+r_n$$ $$p_{n+1}=3q_n+2r_n$$

I can't seem to solve these equations for $p_n$. I tried to solve these for $q_n, r_n$ but I have no idea...

(I don't think the initial conditions will matter. Can anyone give me any hints to find a recurrence relation for $q_n, r_n$ ? Then I'm sure I can handle after that.)

• Hint: Matrices. Let $X_n=\begin{pmatrix}q_n\\ r_n\end{pmatrix}$ then $X_{n+1}=AX_n$ for $A=$ $_____$ hence... – Did May 12 '16 at 16:35
• Whoa didn't think of that... Thanks! – zxcvber May 12 '16 at 17:12

You have $q_{n+1}=q_n+r_n=p_n$, so in general $q_n=p_{n-1}$, and you have
$$r_{n+1}=2q_n+r_n=q_n+(q_n+r_n)=q_n+q_{n+1}=p_{n-1}+p_n\;,$$
so in general $r_n=p_{n-1}+p_{n-2}$. Thus,
$$p_n=q_n+r_n=p_{n-1}+(p_{n-1}+p_{n-2})=2p_{n-1}+p_{n-2}\;.$$
You now have a straightforward second-order homogeneous recurrence for $p_n$, and the other two sequences are completely determined by the $p_n$ sequence.