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!



Regarding sub-additive sequences and Fekete's lemma
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](https://mathoverflow.net/questions/161960/looking-for-a-reference-to-a-classical-formula-for-the-sum-of-the-base-b-digit), 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.


