subadditivity

A sequence ${\{a_n\}}_{n=1}^{\mathrm{\infty }}$ is called subadditive if it 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 following lemma 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 as well.

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].

Title	subadditivity
Canonical name	Subadditivity
Date of creation	2013-03-22 13:52:22
Last modified on	2013-03-22 13:52:22
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	10
Author	bbukh (348)
Entry type	Definition
Classification	msc 39B62
Synonym	subadditive
Related topic	Superadditivity