Fekete lemma ($\lim x_n/n={\inf }_{k\ge 1}{x}_k/k$)

For a real subadditive sequence $(x_n{)}_{n\ge 1}$, the normalized sequence has the extended-real limit of a sequenceNo lower-bound hypothesis is needed for this conclusion. The limit of a sequence is finite precisely when the ratios are bounded below. The example $x_n=-n^2$ is a subadditive sequence with normalized limit of a sequence $-\infty$.

To prove the result, fix $k\ge 1$ and, for $n\ge k$, write $n=qk+r$ with $q\ge 1$ and $0\le r<k$. Iterating subadditivity gives $x_n\le q{x}_k+C_k$, where $C_k=\max (0,x_1,\dots ,x_{k-1})$ and $C_1=0$. Hence ${\mathrm{limsup}}_n{x}_n/n\le x_k/k$ for every $k$. Every ratio is at least their infimum. If that infimum is finite these bounds identify the limit of a sequence; if it is $-\infty$, choosing $k$ with an arbitrarily negative ratio gives convergence to $-\infty$.