## Theorem

Let $\sequence {a_n}_{n \mathop \ge 1}$ be a subadditive sequence.

Then:

$\ds \lim_{n \mathop \to \infty} \frac {a_n} n = \inf_{n \mathop \ge 1} \frac {a_n} n$

## Proof

Let $k \ge 1$.

Let $n \ge 1$.

By Division Theorem, there exist $q \in \N$ and $r \in \set {0, 1, \ldots , k - 1}$ such that:

$n = k q + r$

Thus:

 $\ds \frac {a_n} n$ $=$ $\ds \frac {a_{k q + r} } n$ $\ds$ $\le$ $\ds \frac {a_{k q} + a_r} n$ Definition of Subadditive Sequence $\ds$ $=$ $\ds \frac {a_{\underbrace{k + \cdots + k}_q} + a_r} n$ $\ds$ $\le$ $\ds \frac {q a_k + a_r} n$ Definition of Subadditive Sequence $\ds$ $=$ $\ds \frac {q a_k} {k q + r} + \frac {a_r} n$ $\ds$ $\le$ $\ds \frac {a_k} k + \frac {a_r} n$ $\ds$ $\le$ $\ds \frac {a_k} k + \frac {\max \set {a_0, a_1, \ldots , a_{k - 1} } } n$

By $n \to \infty$, we obtain:

$\ds \forall k \ge 1 : \limsup_{n \mathop \to \infty} \frac {a_n} n \le \frac {a_k} k$

In particular:

$\ds (1): \quad \limsup_{n \mathop \to \infty} \frac {a_n} n \le \inf_{k \mathop \ge 1} \frac {a_k} k$

On the other hand, by definition of infimum:

$\ds \forall n \ge 1 : \inf_{k \mathop \ge 1} \frac {a_k} k \le \frac{a_n} n$

In particular:

$\ds (2): \quad \inf_{k \mathop \ge 1} \frac {a_k} k \le \liminf_{n \mathop \to \infty} \frac {a_n} n$

By Convergence of Limsup and Liminf, $(1)$ and $(2)$ together mean:

$\ds \lim_{n \mathop \to \infty} \frac {a_n} n = \inf_{k \mathop \ge 1} \frac {a_k} k$

$\blacksquare$

## Also known as

Fekete's Subadditive Lemma is often referred to just as Fekete's Lemma.

## Source of Name

This entry was named for Michael Fekete.