Solving recurrence equations

Question

Is there a method to determine the generating function for a mutually recursive recurrence equation?

As an example, consider the following set if equations

$$R_n = R_{n-1}+ 3P_{n-1}; R_0 = 3$$ $$M_n = R_{n-1} + 2P_{n-1};M_0 = 2$$ $$P_n = 5M_{n-1} ;P_0 = 0$$ What I am interested here is to determine, given a value of n, I can find the nth value of R(n), M(n) and P(n) without determining all the values from 1 to n - 1

Answer 1

Hint $$\begin{bmatrix} R_{n}\\ M_{n}\\ P_{n} \end{bmatrix}= \begin{bmatrix} 1&0&3\\ 1&0&2\\ 0&5&0 \end{bmatrix}\cdot \begin{bmatrix} R_{n-1}\\ M_{n-1}\\ P_{n-1} \end{bmatrix}$$ let $$A=\begin{bmatrix} 1&0&3\\ 1&0&2\\ 0&5&0 \end{bmatrix}$$ then we only find $A^n$ it is easy to find it ,because $$A=Q^{-1}diag{(\lambda_{1},\lambda_{2},\lambda_{3})}Q$$ where $\lambda_{i}$ is eigenvalue of $A$,$Q$ is Orthogonal matrix

Solution 2:

since $$M_{n-1}=\dfrac{P_{n}}{5}\Longrightarrow M_{n}=\dfrac{P_{n+1}}{5}$$ then we have $$\dfrac{P_{n+1}}{5}=R_{n-1}+2P_{n-1}\Longrightarrow R_{n-1}=\dfrac{P_{n+1}}{5}-2P_{n-1}$$ so $$\dfrac{P_{n+2}}{5}-2P_{n}=\dfrac{P_{n+1}}{5}-2P_{n-1}+3P_{n-1}$$ then $$P_{n+2}=P_{n+1}+10P_{n}+5P_{n-1},P_{0}=0,P_{1}=10,P_{2}=15$$ then Characteristic equation is $$x^3=x^2+10x+5$$ three roots is $x_{1},x_{2},x_{3}$ then $$P_{n}=A(x_{1})^n+B(x_{2})^n+C(x_{3})^n$$

then It is easy to find it

Answer 2

It should be remarked that the characteristic polynomial of the matrix is $\lambda^3-\lambda^2-10\lambda-5$ just like the characteristic equation for the recurrence for the $P$ values. That is not a coincidence.

Also $M_{n+2}=M_{n+1}+10M_n+5M_{n-1}$ and $R_{n+2}=R_{n+1}+10R_n+5R_{n-1}$

The roots are nothing nice, roughly $r_1=3.896,r_2=-2.350,r_3=-0.546$ so you can get a formula $$P_n=c_1r_1^n+c_2r_2^n+c_3r_3^n$$ Where explicit (but not pretty) formulas (in terms of the various $r_i$) could be given for $c_1,c_2,c_3$ based on $P_0,P_1,P_2.$

We do see that the values grow rapidly (about as fast as $r_1^n$).

If you wanted the values of $P_n,R_n,M_n$ for $n=32$ then you could compute the matrices $A^2,A^4,A^8,A^{16},A^{32}$ by repeated squaring. So you didn't determine all the value from $n=1$ to $n=31,$ just $5$ of them. This multiply and square method can be adapted to deal with any $n.$