= Solution
Choose a variable name $y\ne x$ among the $k$ available names and define
$$
C_1^x(x)=\phi(x),\qquad
C_{m+1}^x(x)=\phi(x)\land\exists y\,[x<y\land C_m^y(y)].
$$
The formula $C_m^y$ is obtained by interchanging the names $x,y$ throughout $C_m^x$, including bound occurrences. Its only free variable is $y$. A permutation of variable names preserves membership in $L^k$, so every formula in this recursion still uses at most the original $k$ names. In particular, bound variables inside a copy of $\phi$ do not accidentally capture the previous comparison: their scope stays inside that copy.
Induction proves that $C_m^x(a)$ holds exactly when there is an increasing $m$-tuple of satisfying elements whose first entry is $a$. Any set of $m$ distinct points in a <linear order> can be put in increasing order. Therefore the <variable-recycling count on a linear order>
$$
\boxed{\phi_n=\exists x\,C_n^x(x)\in L^k}
$$
is the required sentence. This does not use counting quantifiers or additional variable names, and it applies equally to infinite <linear orders>.
Back to article page
