1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – Anurag A Aug 20 '19 at 18:24
  • 3
    $\begingroup$ These are not recurrence relations. Where are the $z_i$? $\endgroup$ – marty cohen Aug 20 '19 at 18:28
  • $\begingroup$ @martycohen, I have edited the post. $\endgroup$ – jonan Aug 20 '19 at 22:11
  • $\begingroup$ Look at the generating functions. $\endgroup$ – marty cohen Aug 21 '19 at 1:02
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$ – jonan Aug 22 '19 at 0:41
  • 1
    $\begingroup$ It depends what is in the denminator. I'll play around a bit and see what happens. $\endgroup$ – marty cohen Aug 22 '19 at 0:51
  • $\begingroup$ wow this got ugly fast. Interesting nonetheless. Thanks $\endgroup$ – jonan Aug 23 '19 at 18:05
  • 1
    $\begingroup$ I would like to see a simpler solution. $\endgroup$ – marty cohen Aug 23 '19 at 22:52
  • $\begingroup$ I have posted something simpler below. However, I am unsure if this approach is rigorous. $\endgroup$ – jonan Aug 24 '19 at 1:22

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.