Fekete's Subadditive Lemma

From ProofWiki
Jump to navigation Jump to search


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


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


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$


\(\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$


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.