2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Can I ask you where does this problem comes from ? $\endgroup$ – Jean Marie Dec 3 '17 at 11:47
  • $\begingroup$ 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"... $\endgroup$ – Jean Marie Dec 3 '17 at 11:53
  • $\begingroup$ No, the stated equations are correct. If the terminology is wrong then I'll change it. $\endgroup$ – J G Dec 3 '17 at 12:07
  • 1
    $\begingroup$ 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 ? $\endgroup$ – Jean Marie Dec 3 '17 at 12:15
  • 1
    $\begingroup$ 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))$$ $\endgroup$ – Maadhav Gupta Dec 3 '17 at 13:03
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Care to add a derivation? $\endgroup$ – orlp Dec 3 '17 at 14:57
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

as you had guessed.

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

enter image description here

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

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.