Existence of a limit associated to an almost subadditive sequence

There are two parts to the story here. Detailed arguments and variants can be found in Pólya-Szegő, Problems and theorems in analysis, Volume I: Series, integral calculus, theory of functions, page 198 and 199 (Exercises 98 and 99 of part I)

Suppose that the sequence $(x_n)_{n \in \mathbb{N}}$ of real numbers is subadditive: $x_{m+n} \leq x_m + x_n$. Consider $L = \inf\limits_{n \in \mathbb{N}} \frac{x_n}{n}$. Either $L = - \infty$ and $\dfrac{a_n}{n}$ diverges properly to $-\infty$, or $$\lim_{n \to \infty} \frac{x_n}{n} = \inf_{n \in \mathbb{N}} \frac{x_n}{n} = L,$$ and in particular the limit exists.

Let $L = \inf\limits_{n \in \mathbb{N}} \frac{x_n}{n}$. The case $L = - \infty$ is easy, so assume $L \gt -\infty$. For $\varepsilon \gt 0$ there is an $m$ such that $\frac{x_m}{m} \lt L + \varepsilon$. Writing $n = km + r$ with $0 \leq r \lt m$ we get $$L \leq \frac{x_{n}}{n} \leq \frac{k \cdot x_m + x_r}{km+r} \leq \frac{x_m}{m}+ \frac{x_r}{n} \leq \frac{x_m}{m} + \frac{C}{n}$$ with $C = \max{\{x_0,\ldots,x_{m-1}\}}.$ For $n \geq C/\varepsilon$ we thus have $\displaystyle L \leq \frac{x_n}{n} \leq \frac{x_m}{m} + \varepsilon \leq L+2\varepsilon$ and thus the limit exists and equals the infimum of the sequence.

The second part is:

Suppose the sequence $(a_n)_{n \in \mathbb{N}}$ satisfies $-1 + a_m + a_n \leq a_{m+n} \leq 1 + a_m + a_n$. Then the limit $L = \lim\limits_{n \to \infty}\frac{a_{n}}{n}$ exists and $L-1 \leq \frac{a_{n}}{n} \leq L+1$.

Note that the sequence $b_n = 1+a_n$ is subadditive: $b_{m+n} \leq b_m + b_n$ hence we can apply the first part to it and find that $$-\infty \leq L = \inf_{n \in \mathbb{N}} \frac{1+a_{n}}{n} = \lim_{n \to \infty} \frac{1+a_{n}}{n} \lt \infty.$$ Similarly, $c_n = 1-a_n$ is subadditive and hence $$- \infty \leq -L = \inf_{n \in \mathbb{N}} \frac{1-a_n}{n} = \lim_{n\to\infty}\frac{1-a_n}{n} \lt \infty.$$ Therefore $L$ is a real number and $L \leq \dfrac{1+a_n}{n}$ together with $-L \leq \dfrac{1-a_n}{n}$ yields the desired estimates $nL - 1 \leq a_n \leq nL+1$ where $L = \lim_{n\to\infty}\frac{a_n}{n}$ also follollows from the above.

These lemmas have many applications. An easy variant of this is that a submultiplicative sequence of non-negative numbers, that is $a_{n+m} \leq a_n a_m$ has the property that $a_{n}^{1/n}$ converges. This can be used for the spectral radius formula in functional analysis.

Recently, quasi-subadditive sequences have received quite a bit of attention in guise of quasi-morphisms with significant applications in group theory, dynamical systems, symplectic geometry, and so on.

A beautiful elementary application is Norbert A'Campo's model of real numbers via almost additive maps $\varphi: \mathbb{Z} \to \mathbb{Z}$ (he calls them slopes), that is functions $\varphi$ satisfying $$\sup\limits_{m,n \in \mathbb{Z}}{|\varphi(m+n) - \varphi(m) - \varphi(n)|} \lt \infty$$ modulo a simple equivalence relation. The basic idea here is that any real number $r$ yields such a map by setting $\phi(n) = \lfloor rn \rfloor$. The paper is highly recommended, as it contains quite a few ingenious constructions and interesting historical remarks.