subadditivity

A sequence ${\{a_n\}}_{n=1}^{\mathrm{\infty }}$ is called subadditive ifit satisfies the inequality

$$a_{n+m}\le a_n+a_m\mathit{\hspace{1em}\hspace{1em}}\text{for all }n\text{ and }m.$$(1)

The major reason for use of subadditive sequences is the followinglemma due to Fekete.

Lemma ([1]).

For every subadditive sequence ${\mathrm{\{}{a}_n\mathrm{\}}}_{n\mathrm{=}\mathrm{1}}^{\mathrm{\infty }}$ the limit$\lim \mathit{}{a}_n\mathrm{/}n$ exists and is equal to $\inf \mathit{}{a}_n\mathrm{/}n$.

Similarly, a function $f(x)$ is subadditive if

$$f(x+y)\le f(x)+f(y)\mathit{\hspace{1em}\hspace{1em}}\text{for all }x\text{ and }y.$$

The analogue of Fekete lemma holds for subadditive functions aswell.

There are extensions of Fekete lemma that do not require (1) to hold for all $m$ and $n$. There are also results that allow one to deduce the rate of convergence to the limit whose existence is stated in Fekete lemma if some kind of both super- (http://planetmath.org/Superadditivity) and subadditivity is present. A good exposition of this topic may be found in [2].