= Solution
This is the <Fekete lemma>, with its possible extended-real limit made explicit. Put $L=\inf_{m\ge1}x_m/m$. Since $x_n\le nx_1$, $L$ cannot be $+\infty$; it may be $-\infty$.
Fix $m\ge1$ and write $n=qm+r$, with $0\le r<m$. Repeated <subadditivity> gives
$$
x_n\le qx_m+x_r,
$$
where for this calculation set $x_0=0$. The finitely many possible remainder terms are bounded. Since $q/n\to1/m$,
$$
\limsup_{n\to\infty}\frac{x_n}{n}\le\frac{x_m}{m}.
$$
This holds for every $m$, whereas $x_n/n\ge L$ by the definition of an <infimum>. If $L$ is finite, the upper and lower bounds agree. If $L=-\infty$, choosing $m$ with arbitrarily negative $x_m/m$ shows that $x_n/n\to-\infty$. Thus
$$
\boxed{\lim_{n\to\infty}\frac{x_n}{n}=\inf_{m\ge1}\frac{x_m}{m}\in[-\infty,\infty).}
$$
A finite real limit is not guaranteed: $x_n=-n^2$ is a <subadditive sequence> and has $x_n/n=-n\to-\infty$. If the limit is intended to be real rather than extended real, one must add a linear lower bound.
Back to article page
