Contractive sequence: $\mathrm{\mid }{x}_{k+2}-x_{k+1}\mathrm{\mid }\le c\mathrm{\mid }{x}_{k+1}-x_k\mathrm{\mid }$ for a fixed $0<c<1$

A sequence $(x_k)$ of reals (Sequences of reals: bounded, eventually, frequently, tails, subsequences) is contractive when there is a real $c$ with

$0<c<1\text{and}\mathrm{\mid }{x}_{k+2}-x_{k+1}\mathrm{\mid }\le c\mathrm{\mid }{x}_{k+1}-x_k\mathrm{\mid }\text{for every }k\in \mathbb{N},$

the order and the absolute value being those of $\mathbb{R}$ (Order on the reals, Basic properties of the absolute value). Such a $c$ is called a contraction constant for $(x_k)$.

The constant must not depend on $k$. This is the whole content of the definition and the only place it can go wrong. A sequence whose consecutive gaps each shrink, so that

$\mathrm{\mid }{x}_{k+2}-x_{k+1}\mathrm{\mid }<\mathrm{\mid }{x}_{k+1}-x_k\mathrm{\mid }\text{for every }k,$

is not contractive on that evidence: what is required is a single $c<1$ working at every index simultaneously. The two conditions really are different: there is a sequence satisfying the second that satisfies the first for no $c<1$ and does not converge, and it is the named counterexample of the companion page, recalled in the remarks below.

The constant is not unique. If $c$ is a contraction constant then so is every $c^{\mathrm{\prime }}$ with $c\le c^{\mathrm{\prime }}<1$, since $c\mathrm{\mid }{x}_{k+1}-x_k\mathrm{\mid }\le c^{\mathrm{\prime }}\mathrm{\mid }{x}_{k+1}-x_k\mathrm{\mid }$ when $\mathrm{\mid }{x}_{k+1}-x_k\mathrm{\mid }\ge 0$ (Basic properties of the absolute value). Statements about contractive sequences therefore quantify over a chosen constant, and the error bound in Every contractive sequence is Cauchy, hence converges, with error bound $\mathrm{\mid }x-x_k\mathrm{\mid }\le c^{k-1}\mathrm{\mid }{x}_2-x_1\mathrm{\mid }\mathrm{/}(1-c)$ for $k\ge 1$ is sharper for a smaller $c$.

Degenerate cases are included. A constant sequence is contractive with every $c\in (0,1)$, all the gaps being $0$. A sequence that is eventually constant is contractive as soon as the inequality holds at the finitely many earlier indices. Nothing in the definition forces the gaps to be positive.

• Where the name comes from. The typical contractive sequence arises by iterating a map: if $f:\mathbb{R}\to \mathbb{R}$ satisfies $\mathrm{\mid }f(u)-f(v)\mathrm{\mid }\le c\mathrm{\mid }u-v\mathrm{\mid }$ for all $u,v$, with $0<c<1$, and $x_{k+1}=f(x_k)$, then $(x_k)$ is contractive with the same $c$, because $\mathrm{\mid }{x}_{k+2}-x_{k+1}\mathrm{\mid }=\mathrm{\mid }f(x_{k+1})-f(x_k)\mathrm{\mid }\le c\mathrm{\mid }{x}_{k+1}-x_k\mathrm{\mid }$. This is the elementary shadow of the Banach fixed point theorem, and The sequence $x_{k+1}=(x_k+1)\mathrm{/}3$ is contractive with $c=1\mathrm{/}3$ and converges to $1\mathrm{/}2$ ↗ is the simplest instance.

• The definition says nothing about a limit, and that is deliberate. It is a condition on consecutive differences only, checkable without knowing where the sequence is going, which is exactly what makes Every contractive sequence is Cauchy, hence converges, with error bound $\mathrm{\mid }x-x_k\mathrm{\mid }\le c^{k-1}\mathrm{\mid }{x}_2-x_1\mathrm{\mid }\mathrm{/}(1-c)$ for $k\ge 1$ useful: convergence and an explicit error bound both fall out of a hypothesis that never mentions the limit.

• Contractive implies the gaps are null but not conversely. From the definition the gaps satisfy $\mathrm{\mid }{x}_{k+1}-x_k\mathrm{\mid }\le c^{k-1}\mathrm{\mid }{x}_2-x_1\mathrm{\mid }$ for $k\ge 1$, which tends to $0$ (For $\mathrm{\mid }r\mathrm{\mid }<1$ the sequence $r^k$ is null, and for $\mathrm{\mid }r\mathrm{\mid }>1$ the sequence $\mathrm{\mid }r{\mathrm{\mid }}^k$ diverges to $+\mathrm{\infty }$); the first gap $\mathrm{\mid }{x}_1-x_0\mathrm{\mid }$ is unconstrained, having no predecessor (Every contractive sequence is Cauchy, hence converges, with error bound $\mathrm{\mid }x-x_k\mathrm{\mid }\le c^{k-1}\mathrm{\mid }{x}_2-x_1\mathrm{\mid }\mathrm{/}(1-c)$ for $k\ge 1$). The converse implication fails badly: gaps tending to $0$ do not even give a Cauchy sequence, which is FALSE: if $\mathrm{\mid }{x}_{k+1}-x_k\mathrm{\mid }\to 0$ then $(x_k)$ is Cauchy.

• The witness separating the two conditions is $x_{k+1}=x_k+1\mathrm{/}{x}_k$ from $x_1=1$ has strictly decreasing consecutive gaps and diverges, so no uniform $c<1$ exists ↗: its consecutive gaps strictly decrease, every ratio of consecutive gaps is below $1$, and still no single $c<1$ works, because those ratios approach $1$. It is what the uniformity requirement above exists to exclude.