Fekete's lemma

1. The lemma

We give a very elegant (and useful) application of the idea of supremum and infimum. This result is attributed to Michael Fekete, and gets applied in many places, including number theory, combinatorics, and analysis. First, a definition.

Definition.

A sequence (₎ of nonnegative terms is subadditive if ₊₊ for all , .

Fekete's lemma.

Let (₎ be a subadditive sequence of nonnegative terms . Then ( ) is bounded below and converges to inf .

Proof.

To see that the sequence is bounded below, just note that ₀ so 0 for each .

Now let =inf . We must prove that .

Subproof.

Let 0 be arbitrary.

Subproof.

Let such that - /2 . There is some such , since if not +/2 would also be a lower bound, contradicting the fact that is the greatest lower bound.

Let be such that /2 for all =0,1,2,,-1 . To find such an just find =max and choose so that / /2 .

Let = .

Subproof.

Let be arbitrary.

Let , such that = + with . So .

Then + + + + + (+/2)+/2 since +/2 . This means that - since by the definition of .

Therefore - .

Therefore 0 - .

For an example of a subadditive sequences, consider ₌. It is easy to check _+
=
+

+. Fekete's lemma says that ( ) converges. So it does: to 0; this isn't terribly difficult and left as an exercise. Other easy examples of subadditive sequences include ₌, for which ( ) is a constant sequence converging to 1.