# Prove the recurrent sequence converges

Following the probability problem

Suppose we have the sequence

$$p_1=\frac{2}{3}$$ $$p_n=\frac{2-p_{n-1}}{3}$$

Obviously if the limit exists, it is $$p_\infty=1/2$$

How to prove convergence?

Observe that $$2p_n-1=\frac{1-2p_{n-1}}{3}$$, from which it follows that $$\left|p_n-\tfrac12\right|=\frac{\bigl|p_{n-1}-\tfrac12\bigr|}{3}=\frac{\bigl|p_{n-2}-\tfrac12\bigr|}{3^2}=\cdots =\frac{\bigl|p_{1}-\tfrac12\bigr|}{3^{n-1}}=\frac{1}{2\cdot 3^n},$$ and thus the distance to $$\tfrac12$$ decreases exponentially fast to $$0$$.

You could show $$p_n=\dfrac12-\dfrac12\left(-\dfrac13\right)^n.$$

• Cool; is there a trick to find it? Jan 2, 2020 at 1:35
• Jan 2, 2020 at 1:36

If you solve the recurrence equation $$p_n=\frac{2-p_{n-1}}{3} \qquad \text{with} \qquad p_1=a$$ you should find that $$p_n=\frac 12\left(1+(-1)^n \frac {1-2a}{3^{n-1}}\right)$$

A simple way could be : let $$p_n=q_n+b$$ and replace to get $$\frac{4 b-2}{3}+\frac{1}{3} q_{n-1}+q_n=0$$ and choosing $$b=\frac 12$$ reduces the equation to $$\frac{1}{3} q_{n-1}+q_n=0\implies q_n=c_1 \left(-\frac{1}{3}\right)^{n-1}\implies p_n=\frac 12+c_1 \left(-\frac{1}{3}\right)^{n-1}$$ and $$p_1=a$$ leads to $$c_1=\frac{2a-1}{2}$$

The key word here is arithmetic geometric sequence.

A sequence $$\{p_n\}_{n\geqslant 1}$$ is arithmetic-geometric if there exists constants $$a$$ and $$b$$ such that $$p_{n+1}=ap_n+b$$ for every $$n \geqslant 1$$.

In what follows, I will assume that $$a\neq 1$$ (otherwise, the sequence is simply arithmetic).

Consider the linear function $$f(x)=ax+b$$. Since $$a\neq 1$$, $$f$$ has a fixed point $$\ell$$ (that is $$f(\ell)=\ell$$). In the example from the OP, we have $$f(x)=\frac{2-x}{3}$$ and $$\ell=\frac{1}{2}$$.

Consider now $$q_n=p_n-\ell$$. Then $$\{q_n\}$$ is geometric of common ratio $$a$$ and first term $$q_0=p_0-\ell$$. Indeed,

$$q_{n+1}=p_{n+1}-\ell = (a p_n + b) - (a\ell + b) = a(p_n - \ell) = a q_n$$

Therefore, we have $$q_n=a^{n-1}q_0$$ so $$p_n = a^{n-1}(p_0-\ell)+\ell$$. In the example from the OP, we have $$p_{n} = \frac{1}{6}\left(\frac{1}{2}\right)^n+\frac{1}{2}$$.

Finally,

• In the case where $$|a|<1$$, the sequence $$\{p_n\}$$ converges to $$\ell$$.
• In the case where $$|a|>1$$, the sequence is divergent.

Let $$f(x)=\frac{2-x}{3}$$. Then $$f'(x)=-\frac{1}{3}$$ and so $$|f'(x)|<1$$. Therefore, $$f$$ is a contraction and so iterating $$f$$ converges to its unique fixed point, no matter what initial point you take (Banach fixed-point theorem).