Proof of Fekete’s subadditive lemma

If there is a $m$ such that $a_m=-\mathrm{\infty }$, then, by subadditivity, we have $a_n=-\mathrm{\infty }$ for all $n>m$. Then, both sides of the equality are $-\mathrm{\infty }$, and the theorem holds. So, we suppose that $a_n\in \text{𝐑}$ for all $n$. Let $L={inf}_n\frac{a_n}{n}$ and let $B$ be any number greater than $L$. Choose $k\ge 1$ such that

For $n>k$, we have, by the division algorithm there are integers $p_n$ and $q_n$ such that $n=p_{n}k+q_n$, and $0\le q_n\le k-1$. Applying the definition of subadditivity many times we obtain:

$$a_n=a_{p_{n}k+q_n}\le a_{p_{n}k}+a_{q_n}\le p_n{a}_k+a_{q_n}$$

So, dividing by $n$ we obtain:

$$\frac{a_n}{n}\le \frac{p_{n}k}{n}\frac{a_k}{k}+\frac{a_{q_n}}{n}$$

When $n$ goes to infinity, $\frac{p_{n}k}{n}$ converges to $1$ and $\frac{a_{q_n}}{n}$ converges to zero, because the numerator is bounded by the maximum of $a_i$ with $0\le i\le k-1$. So, we have, for all $B>L$:

Finally, let $B$ go to $L$ and we obtain

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

Title	Proof of Fekete’s subadditive lemma
Canonical name	ProofOfFeketesSubadditiveLemma
Date of creation	2014-03-18 14:41:50
Last modified on	2014-03-18 14:41:50
Owner	Filipe (28191)
Last modified by	Filipe (28191)
Numerical id	3
Author	Filipe (28191)
Entry type	Proof