= Fekete lemma
{c}
{title2=$\lim x_n/n=\inf_{k\geq1}x_k/k$}
{wiki=Fekete's_lemma}
= Extended-real Fekete lemma
{synonym}
For a real <subadditive sequence> $(x_n)_{n\geq1}$, the normalized <sequence> has the extended-real <limit of a sequence>
$$
\lim_{n\to\infty}\frac{x_n}{n}=\inf_{k\geq1}\frac{x_k}{k}\in[-\infty,\infty).
$$
No 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\geq1$ and, for $n\geq k$, write $n=qk+r$ with $q\geq1$ and $0\leq r<k$. Iterating <subadditivity> gives $x_n\leq qx_k+C_k$, where $C_k=\max(0,x_1,\ldots,x_{k-1})$ and $C_1=0$. Hence $\limsup_n x_n/n\leq 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$.
Back to article page
