Prove the recurrent sequence converges

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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