# When the Solutions of a System of Recurrence Relations converge

I have the following system of recurrence relations:

$$a_{i+1} = 1 + z_1 a_i + z_2 b_i$$ $$b_{i+1} = 1 + z_3 a_i + z_4 b_i$$

I would like to know which conditions $$z_1, z_2, z_3, z_4$$ must satisfy in order for their to exist some solutions.

• Hint: you can write this system of equations as $$\begin{bmatrix}1-z_1 & -z_2\\-z_3&1-z_4\end{bmatrix}\begin{bmatrix}\alpha\\\beta\end{bmatrix}=\begin{bmatrix}1\\1\end{bmatrix}$$Now use row-reduction. – Anurag A Aug 20 '19 at 18:24
• These are not recurrence relations. Where are the $z_i$? – marty cohen Aug 20 '19 at 18:28
• @martycohen, I have edited the post. – jonan Aug 20 '19 at 22:11
• Look at the generating functions. – marty cohen Aug 21 '19 at 1:02

## 2 Answers

I have never learnt the theory of generating functions, but I have studied some ODEs and the stability of dynamical systems. Intuitively, it seems as though this should work. Let me know what you think:

$$\begin{pmatrix} a_{i+1}\\\ b_{i+1} \end{pmatrix} = \begin{pmatrix} z_1 & z_2 \\\ z_3 & z_4 \end{pmatrix} \begin{pmatrix} a_{i}\\\ b_{i} \end{pmatrix} + \begin{pmatrix} 1\\\ 1 \end{pmatrix}$$

We can think about this in the context of systems of ODE's:

$$y' = \begin{pmatrix} z_1 & z_2 \\\ z_3 & z_4 \end{pmatrix} y + \begin{pmatrix} 1\\\ 1 \end{pmatrix}$$

Since we are only concerned with convergence, let us consider the homogeneous case:

$$x' = \begin{pmatrix} z_1 & z_2 \\\ z_3 & z_4 \end{pmatrix} x$$

Finding the eigenvalues:

$$\left( z_1 - \lambda \right) \left( z_4 - \lambda \right) - z_2 z_3 = 0$$

$$\lambda_{1,2} = \frac{z_1 + z_4}{2} \pm \frac{1}{2}\sqrt{z_1^2 + z_4^2 - 2z_1 z_4 + 4z_2 z_3}$$

Suppose that the contents under the square root are positive, then the system is stable if $$\lambda_{1,2} < 0$$ or if:

$$\frac{-z_1 - z_4}{2} > \pm \frac{1}{2}\sqrt{z_1^2 + z_4^2 - 2z_1 z_4 + 4z_2 z_3}$$

Squaring both sides, we get:

$$z_2 z_3 < z_1 z_4$$

Thus, in the case that $$\lambda_{1,2} \in \mathbb{R}$$, the system is stable if $$\det \begin{pmatrix} z_1 & z_2 \\\ z_3 & z_4 \end{pmatrix} > 0$$

This handles the case where $$\lambda_{1,2}$$ is real. For the imaginary case, the real part of $$\lambda_{1,2}$$ is simply $$\frac{z_1 + z_4}{2}$$. The system is stable if $$z_1 + z_4 \leq 0$$.

In particular, the system is asymptotically stable if $$z_1 + z_4 < 0$$.

We can conclude the following:

If $$\left(z_1 - z_4 \right)^2 + 4z_2 z_3 > 0$$, ($$Im(\lambda) = 0$$ ), then the system is stable if $$z_1 z_4 - z_2 z_3 > 0$$

If $$\left(z_1 - z_4 \right)^2 + 4z_2 z_3 < 0$$, ($$Im(\lambda) \neq 0$$), then the system is stable if $$z_1 + z_4 < 0$$

Finally, if $$\left(z_1 - z_4 \right)^2 + 4z_2 z_3 = 0$$, then the matrix has one eigenvalue, $$\lambda = \frac{z_1 + z_4}{2}$$. Clearly, the system is stable if $$z_1 + z_4 < 0$$

Does the stability of such a function provide insight into the convergence of these sequences $${a_i}$$ and $${b_i}$$?

(I did some more grunt work to get the generating functions.)

Write the equations as

$$a_{i+1} = u_0 + u_1 a_i + u_2 b_i$$

$$b_{i+1} = v_0 + v_1 a_i + v_2 b_i$$

Let $$A(x) =\sum_{n=0}^{\infty} a_kx^k$$ and $$B(x) =\sum_{n=0}^{\infty} b_kx^k$$.

The generating function (GF) of the lhs of the first is

$$\begin{array}\\ \sum_{k=0}^{\infty} a_{k+1}x^k &=\frac1{x}\sum_{k=0}^{\infty} a_{k+1}x^{k+1}\\ &=\frac1{x}\sum_{k=1}^{\infty} a_{k}x^{k}\\ &=\frac1{x}(A(x)-a_0)\\ \end{array}$$

The GF of the right side of the first is

$$\begin{array}\\ \sum_{k=0}^{\infty} (u_0 + u_1 a_k + u_2 b_k)x^k &=\sum_{k=0}^{\infty} u_0x^k + \sum_{k=0}^{\infty}u_1 a_ix^k + \sum_{k=0}^{\infty}u_2 b_ix^k\\ &=\dfrac{u_0}{1-x}+u_1A(x)+u_2 B(x)\\ \end{array}$$

Therefore $$\frac1{x}(A(x)-a_0) =\dfrac{u_0}{1-x}+u_1A(x)+u_2 B(x)$$.

Similarly, from the second one, $$\frac1{x}(B(x)-a_0) =\dfrac{v_0}{1-x}+v_1A(x)+v_2 B(x)$$.

The next step is to solve these for $$A(x)$$ and $$B(x)$$.

I will write $$A$$ and $$B$$ for $$A(x)$$ and $$B(x)$$.

From the first,

$$\begin{array}\\ B &=\dfrac1{u_2}(\dfrac1{x}(A-a_0)-\dfrac{u_0}{1-x}-u_1A)\\ &=\dfrac1{u_2}(A(\dfrac1{x}-u_1)-\dfrac{a_0}{x}-\dfrac{u_0}{1-x})\\ &=\dfrac1{u_2}(A(\dfrac1{x}-u_1)-\dfrac{a_0-a_0x+u_0x}{x(1-x)})\\ &=Ap_a(x)+q_a(x)\\ \end{array}$$

where $$p_a(x)=\dfrac{1-u_1x}{u_2x},\\ q_a(x)=-\dfrac{a_0-a_0x+u_0x}{u_2x(1-x)}$$.

Similarly,

$$\begin{array}\\ A &=\dfrac1{v_2}(B(\dfrac1{x}-v_1)-\dfrac{b_0-b_0x+v_0x}{x(1-x)})\\ &=Bp_b(x)+q_b(x)\\ \end{array}$$

where $$p_b(x)=\dfrac{1-v_1x}{v_2x},\\ q_b(x)=-\dfrac{b_0-b_0x+v_0x}{v_2x(1-x)}$$.

Putting the first into this,

$$\begin{array}\\ A &=\dfrac1{v_2}(B(\dfrac1{x}-v_1)-\dfrac{b_0-b_0x+v_0x}{x(1-x)})\\ &=Bp_b(x)+q_b(x)\\ &=(Ap_a(x)+q_a(x))p_b(x)+q_b(x)\\ &=Ap_a(x)p_b(x)+q_a(x)p_b(x)+q_b(x)\\ \text{so}\\ A &=\dfrac{q_a(x)p_b(x)+q_b(x)}{1-p_a(x)p_b(x)}\\ &=\dfrac{-\dfrac{a_0-a_0x+u_0x}{u_2x(1-x)}\dfrac{1-v_1x}{v_2x}-\dfrac{b_0-b_0x+v_0x}{v_2x(1-x)}}{1-\dfrac{1-u_1x}{u_2x}\dfrac{1-v_1x}{v_2x}}\\ &=-\dfrac{\dfrac{a_0-a_0x+u_0x}{u_2x(1-x)}\dfrac{1-v_1x}{v_2x}+\dfrac{b_0-b_0x+v_0x}{v_2x(1-x)}}{1-\dfrac{1-u_1x}{u_2x}\dfrac{1-v_1x}{v_2x}}\dfrac{u_2v_2x^2(1-x)}{u_2v_2x^2(1-x)}\\ &=-\dfrac{(a_0-a_0x+u_0x)(1-v_1x)+u_2x(b_0-b_0x+v_0x)}{(u_2v_2x^2(1-x))-(1-x)(1-u_1x)(1-v_1x)}\\ &=-\dfrac{(a_0-x(a_0-u_0))(1-v_1x)+u_2x(b_0-x(b_0-v_0))}{(1-x)(u_2v_2x^2-(1-u_1x)(1-v_1x))}\\ &=\dfrac{(a_0-x(a_0-u_0))(1-v_1x)+u_2x(b_0-x(b_0-v_0))}{(1-x)((u_1 v_1- u_2 v_2) x^2 -( u_1 + v_1) x + 1)}\\ &=\dfrac{a_0-x(a_0-u_0+v_1a_0)+v_1(a_0-u_0)x^2+b_0u_2x-x^2u_2(b_0-v_0))}{(1-x)((u_1 v_1- u_2 v_2) x^2 -( u_1 + v_1) x + 1)}\\ &=\dfrac{a_0-x(a_0-u_0+v_1a_0-b_0u_2)+x^2(v_1(a_0-u_0)-u_2(b_0-v_0))}{(1-x)((u_1 v_1- u_2 v_2) x^2 -( u_1 + v_1) x + 1)}\\ \end{array}$$

To use partial fractions, we need the roots of $$0 =(u_1 v_1- u_2 v_2) x^2 -( u_1 + v_1) x + 1$$.

If $$u_1v_1 = u_2v_2$$, this is $$0 =-( u_1 + v_1) x + 1 =-c_1x+1$$.

If also $$c_1 = 0$$, the denominator is just $$1-x$$, so the expansion is easy.

If $$c_1 \ne 0$$, the denominator is $$(1-x)(1-c_1x)$$ which has the partial fraction decomposition (see below) of

$$\begin{array}\\ \dfrac1{(1-x)(1-c_1x)} &=\dfrac1{1-c_1}(\dfrac1{1-x}-\dfrac{c_1}{1-c_1x})\\ &=\dfrac1{1-c_1}\sum_{k=0}^{\infty}(1-c_1^{k+1})x^k\\ \end{array}$$

If $$u_1v_1 \ne u_2 v_2$$, the quadratic in the denominator has two roots.

These are

$$\begin{array}\\ r_+, r_- &=\dfrac{u_1+v_1\pm\sqrt{(u_1+v_1)^2-4(u_1 v_1- u_2 v_2)}}{2(u_1 v_1- u_2 v_2)}\\ &=\dfrac{u_1+v_1\pm\sqrt{u_1^2+2u_1v_1+v_1^2-4(u_1 v_1- u_2 v_2)}}{2(u_1 v_1- u_2 v_2)}\\ &=\dfrac{u_1+v_1\pm\sqrt{u_1^2-2u_1v_1+v_1^2+4 u_2 v_2}}{2(u_1 v_1- u_2 v_2)}\\ &=\dfrac{u_1+v_1\pm\sqrt{(u_1-v_1)^2+4 u_2 v_2}}{2(u_1 v_1- u_2 v_2)}\\ \end{array}$$

The denominator is then $$(1-x)(1-r_+x)(1-r_-x)$$ and the growth of the terms depends on $$r_+$$ and $$r_-$$.

I'll stop here.

• Thanks! this is helpful. In particular, I am curious to see what conditions $u_1, u_2, v_1, v_2$ must satisfy in order for the sequences $a_n$ and $b_n$ to converge. Since I am only checking for convergence and I do not care what it converges to, do I need to carry out this process to the end? is the 'partial-fractions' step necessary here? – jonan Aug 22 '19 at 0:41
• It depends what is in the denminator. I'll play around a bit and see what happens. – marty cohen Aug 22 '19 at 0:51
• wow this got ugly fast. Interesting nonetheless. Thanks – jonan Aug 23 '19 at 18:05
• I would like to see a simpler solution. – marty cohen Aug 23 '19 at 22:52
• I have posted something simpler below. However, I am unsure if this approach is rigorous. – jonan Aug 24 '19 at 1:22