## You are here

HomeProof of Fekete's subadditive lemma

## Primary tabs

# 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}<B$ |

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}<B$ |

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

$L=\inf_{n}\frac{a_{n}}{n}=\lim_{n}\frac{a_{n}}{n}$ |

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections