Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)$.
