# How do I solve interdependent recurrence relations?

I have three functions with values given as

\begin{align*} P(0) &= 0 \quad & P(i+1) &= 5M(i)\\ M(0) &= 1 \quad & M(i+1) &= R(i) + 2P(i)\\ R(0) &= 3 \quad & R(i+1) &= R(i) + 3P(i)\,. \end{align*}

If it was a linear recurrence with one function I could solve it using matrices. But here I cannot bring it to a single relationship. Each one is interrelated with the others.

How do I approach this problem?

Eliminate one recurrence at a time, by plugging in.

For instance, you can use the equation $P(i)=5 M(i-1)$ to eliminate every instance of $P(\cdot)$ in each of the other recurrences. Plugging in, we get

$$M(i) = R(i-1) + 10 M(i-2)$$ $$R(i) = R(i-1) + 15 M(i-2).$$

Now you have two inter-related recurrence relations, instead of three; you've eliminated one.

Do it one more time, say to remove each instance of $M(\cdot)$. You get something like

$$R(i) = R(i-1) + 15 R(i-3) + 150 M(i-4).$$

Do it again, to remove the $M(\cdot)$:

$$R(i) = R(i-1) + 15 R(i-3) + 150 R(i-5) + 1500 M(i-7).$$

Keep doing this, and you'll get a summation, say something like:

$$R(i) = R(i-1) + 15 R(i-3) + 150 R(i-5) + \cdots + 15 \times 10^{(i-3)/2} \times M(0)$$

(if $i$ is odd.)

Now you're down to a single recurrence relation. Solve it. Then, use the equations above to derive the solutions for $P(\cdot)$ and $M(\cdot)$.

• Thanks for the quick reply. I have tried this, I am writing a program for this and calculating the value of R,M,P for a particular value i. Is there any fast way algorithmically. – katori Sep 11 '14 at 9:07
• @katori Yes, there is a fast way algorithmically. Solve the recurrences, as D.W. has shown you how, and then just write a program that calculates $P(i)=\frac{4}{5}i(\log i)^2$ or whatever the real answer is (that function's just an example that I made up). – David Richerby Sep 11 '14 at 9:21
• @D.W. I solved the problem. Thanks to your idea. But instead of R(i) I calculated M(i) which was an independent linear recurrence. Then with the help of given relation ships I calculate R(i) and P(i). – katori Sep 16 '14 at 6:39