# Simultaneous recurrence relations: $a_n = a_{n-1} (1 - b_n), b_n = b_{n-1} (1-a_n)$

I want to solve the following simultaneous recurrence relations:

\begin{align*} a_n &= a_{n-1} (1-b_n) \\ b_n &= b_{n-1} (1-a_n). \end{align*}

Initial conditions are $a_1 = b_1 = 1$ and $a_2 + b_2 = 1$. The symmetric case, $a_2 = b_2 = 1/2$, has a simple solution: $a_n = b_n = 1/n$.

I have combined the equations through $a_n + b_n$, $a_n b_n$, and $a_n/b_n$ without getting closer to a solution. If my algebra hasn't failed me, the two equations imply the following:

$$a_n a_{n-2} + a_n a_{n-1} a_{n-2} = a_{n-1}^2 + a_n a_{n-1}^2.$$

If it's of any help, it seems that $a_n$ approaches $2 - 1/a_2$ when $n$ tends to infinity for $a_2 \geq 1/2$.

• Can I ask you where does this problem comes from ? – Jean Marie Dec 3 '17 at 11:47
• Are you sure it's not \begin{align*} a_n &= a_{n-1} (1-b_{n-2}) \\ b_n &= b_{n-1} (1-a_{n-2}). \end{align*} ? Otherwise these equations do not deserve the name "recurrence"... – Jean Marie Dec 3 '17 at 11:53
• No, the stated equations are correct. If the terminology is wrong then I'll change it. – J G Dec 3 '17 at 12:07
• Thanks for the answer to my second question. It isn't a recurrence relationship, because a recurrence relationship gives an explicit way to obtain the nth term. Here, it is implicit : you are not even sure that these equation constrain a unique solution $a_{n+1},b_{n+1}$, not to speak of an explicit formula for them. Besides, could you also answer my first question ? – Jean Marie Dec 3 '17 at 12:15
• I don't know if this helps but $$a_n = a_{n-1} (1-b_n)=a_{n-2}(1-b_{n-1})(1-b_n)=(1-b_2)...(1-b_{n-1})(1-b_n)$$ $$\implies b_n=b_{n-1}(1-(1-b_2)...(1-b_{n-1})(1-b_n))$$ – Maadhav Gupta Dec 3 '17 at 13:03

From the self referential recursions, $$a_n=a_{n-1}(1-b_n)\tag1$$ and $$b_n=b_{n-1}(1-a_n)\tag2$$ Plugging $(2)$ into $(1)$ and $(1)$ into $(2)$ and solving, we get the proper recursions $$a_n=\frac{a_{n-1}(1-b_{n-1})}{1-a_{n-1}b_{n-1}}\tag3$$ $$b_n=\frac{b_{n-1}(1-a_{n-1})}{1-a_{n-1}b_{n-1}}\tag4$$ From which it follows that $$\frac{1-a_n}{1-b_n}=\frac{1-a_{n-1}}{1-b_{n-1}}\tag5$$ and therefore, $$\frac{1-a_n}{1-b_n}=\frac{1-a_2}{1-b_2}\tag6$$ Furthermore, $(1)$ and $(2)$ imply that $$\frac{a_n}{b_n}=\frac{a_{n-1}}{b_{n-1}}\frac{1-b_{n-1}}{1-a_{n-1}}\tag7$$ Therefore, $(6)$ and $(7)$ yield $$\frac{a_n}{b_n}=\frac{a_2}{b_2}\left(\frac{1-b_2}{1-a_2}\right)^{n-2}\tag8$$ Solving $(6)$ and $(8)$ simultaneously, we get $$a_n=\frac{\frac{1-a_2}{1-b_2}-1}{\frac{b_2}{a_2}\left(\frac{1-a_2}{1-b_2}\right)^{n-1}-1}\tag9$$ and $$b_n=\frac{\frac{1-b_2}{1-a_2}-1}{\frac{a_2}{b_2}\left(\frac{1-b_2}{1-a_2}\right)^{n-1}-1}\tag{10}$$

If $a_2\gt b_2$, then $(9)$ says $$\lim_{n\to\infty}a_n=\frac{a_2-b_2}{1-b_2}\tag{11}$$ and $(10)$ says $$\lim\limits_{n\to\infty}b_n=0\tag{12}$$

If $a_2\lt b_2$, then $(9)$ says $$\lim_{n\to\infty}a_n=0\tag{13}$$ and $(10)$ says $$\lim\limits_{n\to\infty}b_n=\frac{b_2-a_2}{1-a_2}\tag{14}$$

Given $a_2,b_2,\;$ let $\; y := (1-a_2)/(1-b_2),\; x := (a_2/b_2) y^{2-n}.\;$ Then $\; a_n=x(1-y)/(x-y),\;$ $b_n=(1-y)/(x-y),\;$ assuming no division by zero. If $y>1$, then $x\to\infty$ as $n\to\infty$. This implies $a_n\to 1-y$ and $b_n\to 0,\;$ and if $\;a_2+b_2=1,\;$ then $y=-1+1/a_2, 1-y=2-1/a_2.$

Notice that $(1-a_n)/(1-b_n)$ doesn't depend on $n$, but $a_n/b_n=(a_2/b_2)((1-a_2)/(1-b_2))^{2-n}$.

• Care to add a derivation? – orlp Dec 3 '17 at 14:57

Since$$b_n=1-\frac{a_n}{a_{n-1}}$$ we get $$1-\frac{a_n}{a_{n-1}}=\left(1-\frac{a_{n-1}}{a_{n-2}}\right)(1-a_n)$$ Multiplying the both sides by $a_{n-1}a_{n-2}$ gives $$a_{n-1}a_{n-2}-a_na_{n-2}=a_{n-1}a_{n-2}-a_na_{n-1}a_{n-2}-a_{n-1}^2+a_na_{n-1}^2,$$ i.e. $$a_{n-1}^2(a_n-1)=a_na_{n-2}(a_{n-1}-1)$$ Dividing the both sides by $a_{n}a_{n-1}$ gives $$\frac{a_{n-1}(a_n-1)}{a_{n}}=\frac{a_{n-2}(a_{n-1}-1)}{a_{n-1}}$$ So, if we define $$c_n=\frac{a_{n-1}(a_n-1)}{a_n}$$ then we have $$c_n=c_{n-1}=\cdots =c_2=\frac{a_1(a_2-1)}{a_2}=-\frac{b_2}{a_2}:=a$$ So, $$\frac{a_{n-1}(a_n-1)}{a_n}=a\implies \frac{1}{a_n}+\frac{a}{a_{n-1}}=1\implies d_n-d_{n-1}=\frac{1}{(-a)^n}$$ where $$d_n=\frac{1}{(-a)^n}\cdot\frac{1}{a_n}$$

So, for $n\ge 2$, we have $$d_n=d_1+\sum_{k=2}^{n}\frac{1}{(-a)^k}=-\frac{1}{a}+\frac{a}{a+1}\left(\frac{1}{a^2}-\frac{1}{(-a)^{n+1}}\right)$$ which holds for $n=1$.

So, we get $$a_n=\frac{a+1}{1-(-a)^n},\qquad b_n=\frac{a+1}{1-(-a)^n}(-a)^{n-1},$$ i.e. $$\color{red}{a_n=\frac{1}{\displaystyle\sum_{k=0}^{n-1}\left(\dfrac{b_2}{a_2}\right)^k},\qquad b_n=\frac{\left(\dfrac{b_2}{a_2}\right)^{n-1}}{\displaystyle\sum_{k=0}^{n-1}\left(\dfrac{b_2}{a_2}\right)^k}}$$

(see figure below). Let us copy the "recurrence" relationships for being able to make reference to them later:

\tag{1}\begin{align*} (a) \ \ \ \ \ a_n &= a_{n-1} (1-b_n) \\ (b) \ \ \ \ \ b_n &= b_{n-1} (1-a_n). \end{align*}

Let $P_k=(a_k,b_k)$ with point $P_1(1,1)$ and $P_2(a_2,b_2)=(r,1-r).$

It means that we have taken $r:=a_2$ as main parameter. Let

$$c:=\tfrac{b_2}{a_2}=\tfrac{1-r}{r}=\tfrac{1}{r}-1,$$

Let us show that:

$$\tag{2}P_n=(a_n,b_n) \ \ \text{with} \ \ \begin{cases}a_n=\frac{1-c}{1-c^n}\\b_n=c^{n-1}a_n=c^{n-1}\frac{(1-c)}{1-c^n}\end{cases}$$

Indeed:

It is straightforward to verify that (2) holds in the general case ; for example (1)(a) is equivalent to the following identity:

$$\frac{1-c}{1-c^{n}}=\frac{1-c}{1-c^{n-1}}\left(1-\frac{c^{n-1}-c^n}{1-c^{n}}\right)$$

valid for any $c\ne 1$ and any $n \in \mathbb{N}$.

(one can check in particular that (2) is true for $n=1$ and $n=2$).

The limit point is either on the horizontal or the vertical axis:

$$P_{\infty}=(a_{\infty},b_{\infty})=\begin{cases}(0,2-\tfrac1r) \ \ \text{if} \ \ r \le \tfrac12\\(2-\tfrac1r,0) \ \ \text{if} \ \ r \ge \tfrac12\end{cases}.$$

Remark: whatever the value of $r$, all points $P_k=(a_k,b_k)$ are aligned on the line joining point $P_1=(1,1)$ to point $P_{\infty}.$

An exemple is shown with $r=0.6$ on the figure.

Remark: I think that it is better to use the following "explicit" expressions given by Somos ; compared with the initial expressions, they express a "true" (crossed) recurrence relationship between the $a_n$ and the $b_n$ :

$$\begin{cases}a_n = a_{n-1}(1-b_{n-1})/(1-a_{n-1}b_{n-1})\\b_n=b_{n-1}(1-a_{n-1})/(1-a_{n-1}b_{n-1})\end{cases}.$$

With these expressions, we can work in a completely clean way, by using a recurrence reasoning.

For the figure, points $P_2 (a_2=r, b_2=1-r)$ have been chosen with a regular step (1/30) for $r$.

• I have completely modified my answer. – Jean Marie Dec 3 '17 at 17:48