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

  • $\begingroup$ 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. $\endgroup$
    – katori
    Sep 11 '14 at 9:07
  • 1
    $\begingroup$ @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). $\endgroup$ Sep 11 '14 at 9:21
  • $\begingroup$ @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). $\endgroup$
    – katori
    Sep 16 '14 at 6:39

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.