0

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.)

zxcvber
  • 2,081

1 Answers1

1

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.

Brian M. Scott
  • 616,228