Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 214 / 1 / a

Let $\alpha ={\inf }_{k\ge 1}{x}_k/k$. The relevant version of the Fekete lemma is the extended-real Fekete lemma: $\alpha$ may be $-\infty$, but cannot be $+\infty$ because $x_1$ is real. We show that this is exactly the limit of a sequence.

Fix $k\ge 1$ and, for $n\ge k$, write $n=qk+r$, where $q\ge 1$ and $0\le r<k$. Iterating the defining inequality gives $x_{qk}\le q{x}_k$. If $r>0$, it also gives $x_n\le q{x}_k+x_r$; if $r=0$, there is no remainder term. Thus, with $C_k=\max (0,x_1,\dots ,x_{k-1})$ and $C_1=0$,As $n\to \infty$, $q/n\to 1/k$, so ${\mathrm{limsup}}_n{x}_n/n\le x_k/k$. This holds for every positive $k$. On the other hand every $x_n/n\ge \alpha$. If $\alpha$ is finite, these two bounds give the desired equality. If $\alpha =-\infty$, for every real $M$ choose $k$ with $x_k/k<M-1$; the same upper bound makes $x_n/n<M$ for all sufficiently large $n$. ThereforeThe index $k=0$ is excluded because its ratio is undefined, and $x_0$ is irrelevant since the defining inequality was required only at positive indices. If the printed word “limit of a sequence” is interpreted as a finite real limit of a sequence, an additional lower bound is necessary: $x_n=-n^2$ defines a subadditive sequence but $x_n/n=-n\to -\infty$. The extended-real statement is the correct unrestricted conclusion.