Fekete’s subadditive lemma

Let ${(a_n)}_n$ be a subadditive sequence in $[-\mathrm{\infty },\mathrm{\infty })$. Then, the following limit exists in $[-\mathrm{\infty },\mathrm{\infty })$ and equals the infimum of the same sequence:

$$\underset{n}{lim}\frac{a_n}{n}=\underset{n}{inf}\frac{a_n}{n}$$

Although the lemma is usually stated for subadditive sequences, an analogue conclusion is valid for superadditive sequences. In that case, for ${(a_n)}_n$ a subadditive sequence in $(-\mathrm{\infty },\mathrm{\infty }]$, one has:

$$\underset{n}{lim}\frac{a_n}{n}=\underset{n}{sup}\frac{a_n}{n}$$

The proof of the superadditive case is obtained by taking the symmetric sequence ${(-a_n)}_n$ and applying the subadditive version of the theorem.

Title	Fekete’s subadditive lemma
Canonical name	FeketesSubadditiveLemma
Date of creation	2014-03-19 22:15:10
Last modified on	2014-03-19 22:15:10
Owner	Filipe (28191)
Last modified by	Filipe (28191)
Numerical id	4
Author	Filipe (28191)
Entry type	Theorem