0
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.