A work-function growth bound at injective configurations extends to all configurations

Fix a metric space $M$, $k\ge1$ servers, and an initial configuration $C_0$ occupying $k$ distinct points. Let $\sigma_1,\sigma_2$ be request sequences and $u\in\mathbb R$.

Statement. If

then the same inequality holds for every configuration $X$, degenerate ones included.

Role. The work-function growth bounds that drive the $k$-server upper bounds --- the $3\,\mathrm{OPT}$ bound for two servers, the $(k+1)\,\mathrm{OPT}$ bound on spaces of $k+1$ and of $k+2$ points, and the $2k\,\mathrm{OPT}$ bound of Koutsoupias--Papadimitriou on general spaces --- are all of the form "one step of the work function grows by at most $u_t$ at every configuration", and their classical proofs give the bound only at configurations occupying $k$ distinct points. This principle upgrades any such bound to all configurations at once, so the two formulations coincide whenever the servers start at distinct points.

Proof idea. Given an arbitrary target $Y$ and $\varepsilon>0$, choose an injective $X$ with $\widehat w_{\sigma_1}(X)+\lVert X-Y\rVert\le\widehat w_{\sigma_1}(Y)+\varepsilon$, which is possible because for an injective start the work function is the Lipschitz extension of its injective restriction. Then

using the Lipschitz property, then the hypothesis at $X$, then the choice of $X$; letting $\varepsilon\to0$ finishes.

The hypothesis on $C_0$ is necessary: for a degenerate start the conclusion acquires an additive slack proportional to the distance from $C_0$ to the nearest injective configuration.