When the Solutions of a System of Recurrence Relations converge

Question

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.

Answer 1

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}$?

Answer 2

(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.