Regarding sub-additive sequences and Fekete's lemma A non-negative sequence $\{a_n\}$ is sub-additive if $a_{m+n}\leq a_m + a_n.$ Fekete's lemma says that for any non-negative sub-additive sequence:
$$\lim_{n\to\infty} \frac{a_n}{n} = \inf_{n} \frac{a_n}{n}.$$
Of course, one way to show this would be to show that $\frac{a_n}{n}$ is non-increasing, but I have seen no proof of Fekete's lemma like this, so I suspect this is not true. Can you give me an example of a non-negative sub-additive sequence $\{a_n\}$ for which $\frac{a_n}{n}$ is not non-increasing? Thanks!
 A: Here is another "natural" example. Fix an integer $b \ge 2$ and let $s_b(n)$ denote, for each $n \in \mathbf N^+$, the sum of the $b$-digits of $n$. Then $s_b$ is subadditive: This comes, e.g., from the first of the identities mentioned here, together with the fact that also the fractional part is subadditive, which in turn is a consequence of the following:
$$
\forall x, y \in \mathbf R: \{x\} + \{y\} = \{x+y\} + \lfloor \{x\} + \{y\} \rfloor.
$$
Now observe that, for all $n \in \mathbf N^+$, 
$$
\frac{s_b(b^n)}{b^n} = \frac{1}{b^n} < \frac{2}{b^n+1} = \frac{s_b(b^n + 1)}{b^n + 1}.
$$
Therefore, the sequence $\mathbf N^+ \to \mathbf R: n \mapsto s_b(n)/n$ is not [eventually] non-increasing.
A: Here's an example from nature, but for superadditive sequences.  Fekete's Lemma for superadditive sequences says 
$$\lim_{n\to\infty} \frac{a_n}{n} = \sup_{n} \frac{a_n}{n}.$$
For a CW complex $X$, we can look at the Lusternik-Schnirelmann category of the skeleta
$X_n$ as $n$ varies (actually, the relative category $\mathrm{cat}_X(X_n)$), and define
a sequence 
$$
\sigma_X (k) = \inf\{ n \mid \mathrm{cat}_X(X_n) \geq k \}.
$$
It can be proved that this sequence is always superadditive, and it contains lots of good information about the space $X$, so it is nice to determine -- or estimate -- the sequence if possible.
One big challenge to people studying L-S category is to determine the category of the symplectic groups $Sp(n)$.  It has been shown that for $n\geq 3$, the sequence
$\sigma_{Sp(n)}$ begins $(0,3,7,10,18,21,\ldots)$.  The ratios are
$$
3 < {7\over 2} > {10\over 3} < {18\over 4} > {21\over 5}
$$
