Finding $\lim_{n\to\infty} \frac{z_{n}}{z_{n-1}}$ where $3z_{n}=z_{n-1}+z_{n-2}+z_{n-1}z_{n-2}$

Solution 1:

Dividing both sides by $z_{n-1}$ gives

$$3b_n=1+\frac{1}{b_{n-1}}+z_{n-2}$$

Since $z_n\to 0$, $z_n>0$ for $n\geq 1$, and the solutions to

$$3x=1+\frac{1}{x}$$

are negative and positive respectively, it is sufficient to prove that $b_n$ converges to prove that

$$\lim_{n\to\infty} b_n= \frac{1+\sqrt{13}}{6}$$

Now, it is easy to prove from induction that $z_n<.9^n$ for all $n\geq 2$. We can manually check that this is the case for $n\in\{2,3,...,11\}$. Then for $n>11$ we have

$$z_n=\frac{1}{3}\left(z_{n-1}+z_{n-2}+z_{n-1}z_{n-2}\right)$$

$$<\frac{1}{3}\left(.9^{n-1}+.9^{n-2}+.9^{n-1}.9^{n-2}\right)$$

Since $n>11$ we have that $.9^n<\frac{1}{3}$. This then gives us

$$=\frac{1}{3}\left(\frac{.9^{n}}{.9}+\frac{.9^{n}}{.9^2}+\frac{.9^{n}.9^{n}}{.9^3}\right)$$

$$<\frac{1}{3}\left(\frac{.9^{n}}{.9}+\frac{.9^{n}}{.9^2}+\frac{.9^{n}}{3\cdot.9^3}\right)$$

$$=9^n\left(\frac{6130}{6561}\right)<.9^n$$

(this also provides a proof that $z_n\to 0$). Next, we will prove by induction that $\frac{7}{10}<b_n<\frac{10}{11}$ for $n\geq 6$. We can manually check that this is the case for $n\in\{6,7,...,14\}$. For $n>14$ we have

$$b_n=\frac{1}{3}+\frac{1}{3b_{n-1}}+\frac{z_{n-2}}{3}<\frac{1}{3}+\frac{1}{3\cdot \frac{7}{10}}+\frac{.9^{n-2}}{3}$$

$$=\frac{17}{21}+\frac{100}{243}.9^n$$

Since $n>14$ this implies $.9^n<\frac{23}{100}$ which gives us

$$<\frac{17}{21}+\frac{100}{243}\cdot \frac{23}{100}=\frac{1538}{1701}<\frac{10}{11}$$

For the lower bound we have

$$b_n=\frac{1}{3}+\frac{1}{3b_{n-1}}+\frac{z_{n-2}}{3}$$

$$>\frac{1}{3}+\frac{1}{3\cdot \frac{10}{11}}=\frac{7}{10}$$

as desired. In fact, we really will only need this lower bound for the rest of the proof. Define $c_n=|b_n-b_{n-1}|$. Then

$$c_n=b_n-b_{n-1}=\left|\frac{1}{3b_{n-1}}-\frac{1}{3b_{n-2}}+\frac{z_{n-2}-z_{n-3}}{3}\right|$$

$$\leq \left(\frac{1}{3b_{n-1}b_{n-2}}\right)|b_{n-1}-b_{n-2}|+\frac{z_{n-2}+z_{n-3}}{3}$$

$$=\left(\frac{1}{3b_{n-1}b_{n-2}}\right)c_{n-1}+\frac{z_{n-2}+z_{n-3}}{3}$$

Importantly, using our lower bound from above we have

$$\frac{1}{3b_{n-1}b_{n-2}}<\frac{1}{3\left(\frac{7}{10}\right)^2}=\frac{100}{147}<.7$$

Since $z_n<.9^n$ for all $n\geq 2$, we know that $n\geq 5$ we have

$$\frac{z_{n-2}+z_{n-3}}{3}<.91^{n-5}$$

Then for these $n\geq 5$ we have

$$c_n<.7 c_{n-1}+.91^{n-5}$$

Now, we will prove by induction that $c_n<.99^n$ for all $n\geq 5$. We can manually check that this is true for $n\in\{5,6,...,21\}$. For $n>21$ we have

$$c_n<.7 .99^{n-1}+.91^{n-5}=.99^n\left[\frac{70}{99}+\left(\frac{100}{91}\right)^5\cdot \left(\frac{91}{99}\right)^n\right]$$

However, since $n>21$ we have

$$\left(\frac{91}{99}\right)^n<\frac{180969322079}{990000000000}$$

which gives us

$$<.99^n\left[\frac{70}{99}+\left(\frac{100}{91}\right)^5\cdot \frac{180969322079}{990000000000}\right]=.99^n$$

as desired. We conclude that $|b_n-b_{n-1}|<.99^n$ (at least for $n\geq 5$). But at this point we are basically done! It is well known that this property implies the sequence in question is Cauchy (see here for example just replacing $.5$ with $.99$). Thus, $b_n$ converges and as shown above this implies

$$\lim_{n\to\infty}b_n=\frac{1+\sqrt{13}}{6}$$

Solution 2:

Enlightened by QC_QAOA's answer and helpful comments, I figure out a proof. I will present it in a way that shows how I could come up with such a proof.

Dividing by $z_{n-1}$ on both sides of (1), one has $$ 3b_n = 1+\frac{1}{b_{n-1}}+z_{n-2}\;.\tag{2} $$ which implies that $$ |b_{n}-b_{n-1}|=\frac1{3|b_{n-1}b_{n-2}|}\cdot |b_{n-1}-b_{n-2}|+\frac{z_{n-2}-z_{n-3}}{3}\tag{3} $$ We will use (3) to show that $(b_n)$ is Cauchy.

Observe that $\lim_{n\to \infty}z_n=0$ and $b_n>0$ for all $n>1$ (see this) . Thus, if the limit of $b_n$ exists: $\lim_{n\to\infty}b_n=b$, then it follows from (2) that $ 3b=1+\frac1{b}, (b>0), $ and thus $$b=\frac16(1+\sqrt{13})=:\alpha\approx 0.768\pm 0.001.\tag{4}$$ This quantity suggests that if we fix a number $r$ such that $0<r<\alpha$, then $b_n>r$ for all sufficiently large $n$. We will choose later this $r$ and prove by induction that it is indeed a lower bound for $b_n$ with large $n$. On the other hand, if we have such $r$, (3) implies that $$ |b_n-b_{n-1}| \leq \frac{1}{3r^2}|b_{n-1}-b_{n-2}|+\frac13(|z_{n-2}|+|z_{n-3}|)\tag{5} $$

This answer shows that $|z_n|\le q^n$ for all sufficiently large $n$ where $0<q<1$; the answer also shows that one also has some flexibilities to choose such $q$, which we will take advantage of later. Inserting $|z_n|\le q^n$ into (5) one has $$ |b_n-b_{n-1}| \leq R|b_{n-1}-b_{n-2}|+Kq^{n}\;,\quad R:=\frac{1}{3r^2},K:=\frac13(q^{-2}+q^{-3})\tag{6} $$ By changing finitely many values of $b_n$, which does not affect convergence, we can assume that (6) is true for all $n\geq 1$. Applying (6) recursively we get $$ \begin{align} |b_n-b_{n-1}| &\leq R(R|b_{n-2}-b_{n-3}|+Kq^{n-1})+Kq^n\\ &=R^2|b_{n-2}-b_{n-3}|+RKq^{n-1}+Kq^n\\ &\leq R^2( R|b_{n-3}-b_{n-4}|+Kq^{n-1} )+RKq^{n-1}+Kq^n\\ &= R^3|b_{n-3}-b_{n-4}| + R^2Kq^{n-1}+RKq^{n-1}+Kq^n\\ &\leq \cdots\\ &\leq R^{n-2}|b_2-b_1|+K(R^{n-3}q^3+\cdots +Rq^{n-1}+q^n)\\ &=R^{n-2}|b_2-b_1|+KCR^n \end{align}\tag{7} $$ where $$ C = (\frac{q}{R})^3 +(\frac{q}{R})^4+\cdots+(\frac{q}{R})^n \le \frac{1}{1-q/R} $$ where $q$ and $R$ will be chosen (by choosing $r$) so that $0<q/R<1$ and $0<R<1$. Consequently, $$ |b_n-b_{n-1}|\le \left(|b_2-b_1|+\frac{KR^2}{1-q/R}\right)R^{n-2} $$ which implies that $(b_n)$ is Cauchy by the triangle inequality and the fact that $\sum R^n<\infty$.

In order to complete the proof, it suffices to

• choose $r$ and $q$ so that $$ 0<r<\alpha,\quad \frac{1}{3r^2}<1,\quad 0<q<1,\quad |z_n|\le q^n,\quad 3qr^2<1 $$

• show that $b_n>r$ for all sufficiently large $n$.

The first two constrains show we need that $\frac{1}{\sqrt{3}}\approx 0.577 < r < \alpha\approx 0.768$. On the other hand, estimates in this answer show that we need $q\in (\alpha,1)$ so that $0<3q^2-q-1<1$. So by the last constrain, we need $q\in (\alpha,1/(3r^2))$ so that $0<3q^2-q-1<1$. At this point, it is not hard to see that $r=0.6$ and $q=0.9$ would work.

Now we show that $b_n>0.6$ for large $n$. In order to do that, we choose a potential upper bound $0.9>\alpha$ for $b_n$ and prove by induction that $0.6<b_n<0.9$ for large $n$. (One may tune the upper bound to help the induction.)

The induction step is easy. By (2) and $|z_n|\le q^n$, and the induction hypothesis that $0.6<b_k<0.9$ for all $N<k<n$ (where $N$ is chosen a priori that $z_n$ is sufficiently small and $b_N\in (0.6,0.9)$), we have $$ b_{n}\le \frac13+\frac{1}{3\times 0.6}+z_{n-2}/3=0.889+z_{n-2}/3 <0.9 $$ and $$ b_{n}\ge \frac13+\frac{1}{3\times 0.9}\approx 0.7037\pm 0.0001 > 0.6 $$

In order to get a base case, one can use a computer to calculate explicitly an $N$ such that $b_N\in (0.6,0.9)$ and $z_{N}<0.003$ using the recursive formula (2) and (1). It turns out that when $N=26$, $b_{26}\approx 0.768 \pm 0.001 \in (0.6,0.9)$ and $z_{26}\approx 0.0024\pm 0.0001<0.003$.