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...
Please help me.
(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.)
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.