Proof of Fekete’s subadditive lemma

If there is a $m$ such that $a_{m}=-\infty$, then, by subadditivity, we have $a_{n}=-\infty$ for all $n>m$. Then, both sides of the equality are $-\infty$, and the theorem holds. So, we suppose that $a_{n}\in\textbf{R}$ for all $n$. Let $L=\inf_{n}\frac{a_{n}}{n}$ and let $B$ be any number greater than $L$. Choose $k\geq 1$ such that

 $\frac{a_{k}}{k}

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\leq q_{n}\leq k-1$. Applying the definition of subadditivity many times we obtain:

 $a_{n}=a_{p_{n}k+q_{n}}\leq a_{p_{n}k}+a_{q_{n}}\leq p_{n}a_{k}+a_{q_{n}}$

So, dividing by $n$ we obtain:

 $\frac{a_{n}}{n}\leq\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\leq i\leq k-1$. So, we have, for all $B>L$:

 $L\leq\lim_{n}\frac{a_{n}}{n}\leq\frac{a_{k}}{k}

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

 $L=\inf_{n}\frac{a_{n}}{n}=\lim_{n}\frac{a_{n}}{n}$
Title Proof of Fekete’s subadditive lemma ProofOfFeketesSubadditiveLemma 2014-03-18 14:41:50 2014-03-18 14:41:50 Filipe (28191) Filipe (28191) 3 Filipe (28191) Proof