The sequence $x_{k+1} = (x_k + 1)/3$ is contractive with $c = 1/3$ and converges to $1/2$

Fix any $a \in \mathbb{R}$ and let $(x_k)$ be the sequence with $x_0 = a$ and

$x_{k+1} = \frac{x_k + 1}{3} \qquad (k \in \mathbb{N}).$

Then $(x_k)$ is contractive with contraction constant $c = 1/3$ (Contractive sequence: $|x_{k+2} - x_{k+1}| \le c\,|x_{k+1} - x_k|$ for a fixed $0 < c < 1$), and

$\lim_{k} x_k = \frac{1}{2},$

whatever the starting value $a$ is. Moreover Every contractive sequence is Cauchy, hence converges, with error bound $|x - x_k| \le c^{k-1}|x_2 - x_1|/(1-c)$ for $k \ge 1$ supplies the error bound $|1/2 - x_k| \le 3^{\,-(k-1)}|x_2 - x_1|/(1 - 1/3)$ for $k \ge 1$, which is computable from the first three terms alone.

The limit $1/2$ is the unique solution of $L = (L+1)/3$, that is the unique fixed point of the map $u \mapsto (u+1)/3$. This is the smallest honest instance of the Banach fixed point theorem: a contraction on $\mathbb{R}$ has one fixed point, and every orbit converges to it.

• The starting value is genuinely arbitrary. Nothing in the verification uses anything about $a$, and the limit does not depend on it. What does depend on it is the error bound, through $|x_2 - x_1|$, which for this recursion equals $|a - 1/2| \cdot 2/9$.

• Contractivity is exact here, not an estimate. Step 1.2 gives equality, $|x_{k+2} - x_{k+1}| = \tfrac13|x_{k+1} - x_k|$, so for every starting value $a \ne 1/2$ the constant $c = 1/3$ is the smallest admissible one; for $a = 1/2$ the sequence is constant, every gap is $0$, and every $c \in (0,1)$ is admissible (Contractive sequence: $|x_{k+2} - x_{k+1}| \le c\,|x_{k+1} - x_k|$ for a fixed $0 < c < 1$). The error bound of Every contractive sequence is Cauchy, hence converges, with error bound $|x - x_k| \le c^{k-1}|x_2 - x_1|/(1-c)$ for $k \ge 1$ is as sharp as that theorem can make it. Contrast $x_{k+1} = x_k + 1/x_k$ from $x_1 = 1$ has strictly decreasing consecutive gaps and diverges, so no uniform $c < 1$ exists, where the ratio of consecutive gaps tends to $1$ and no admissible constant exists at all.

• Why a fixed point is forced. The limit satisfies the recursion equation because a sequence and its shift have the same limit (Convergence depends only on the tail) and the algebra of limits transports the right-hand side. This is the same move as in The Babylonian sequence $x_1 = 2$, $x_{k+1} = (x_k + 2/x_k)/2$ decreases to $\sqrt{2}$ and The sequence $x_1 = 1$, $x_{k+1} = \sqrt{2 + x_k}$ increases to $2$; the difference is that here convergence comes from contractivity rather than from monotonicity, and no monotonicity is available, since for $a > 1/2$ the sequence decreases and for $a < 1/2$ it increases while for $a = 1/2$ it is constant.