Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to prove that a sequence lives in a specific interval; I did prove that lives in a bigger interval, but not in the one I want.

Let $ a_n $ a sequence such that for any n,m
$$a_n + a_m -1 < a_{n+m} < a_n + a_m +1 $$ Prove that the sequence $ (a_n) / n $ converges ( to $L$) and then prove that $$ a_n \in \left(nL - 1,nL+1 \right) $$

I proved everything, but I proved that lies in $$ \left( nL - 2,nL+2 \right) $$ I can´t bound it more.

share|cite|improve this question
Put $b_n = a_{n} + 1$ then $b_{n+m} \leq b_{n} + b_{m}$ and thus $$L = \lim_{n \to \infty} \frac{a_{n} + 1}{n} = \inf_{n} \frac{a_{n} + 1}{n}. \qquad \text{Moreover, } \frac{a_{n} + 1}{n} \geq L.$$ Similarly with $c_n = 1-a_n$ with $\dfrac{c_n}{n}$ converging to $-L$ and thus $$\frac{1-a_n}{n} \geq -L.$$ This is a classic from Pólya-Szegő, Exer. 98/99, by the way. (they attribute it to Fekete). – t.b. Aug 14 '11 at 20:20
Oh, sorry, I messed up the link. This one should work: it's Pólya-Szegő, Problems and theorems in analysis, Volume I: Series, integral calculus, theory of functions. It's part of the detailed statement that for a subbadditive sequence $d_{n + m} \leq d_{n} + d_{m}$ either there is a lower bound of $d_n/n$ and then $L \leq \frac{d_n}{n}$ and thus the limit equals the infimum or $\frac{d_n}{n}$ diverges properly to $-\infty$. The second case can't happen here because $c_n / n $ has $-L$ as lower bound. – t.b. Aug 14 '11 at 20:50
@Theo: Wikipedia has a reference (found on Subadditivity) to the paper of Fekete: Fekete, M. "Uber die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit. ganzzahligen Koeffizienten." Mathematische Zeitschrift 17 (1923), pp. 228–249. – Asaf Karagila Aug 14 '11 at 20:56
@Asaf: Thanks (man, wanna challenge me with references?! :p) I know that paper, but after looking through it several times I found myself unable to find a compelling reason why exactly it is mentioned by PS... :) – t.b. Aug 14 '11 at 20:59
@Daniel: Please don't use subjective titles like "It's difficult", "it's hard", etc. – Arturo Magidin Aug 14 '11 at 22:55
up vote 10 down vote accepted

There are two parts to the story here. Detailed arguments and variants can be found in Pólya-Szegő, Problems and theorems in analysis, Volume I: Series, integral calculus, theory of functions, page 198 and 199 (Exercises 98 and 99 of part I)

Suppose that the sequence $(x_n)_{n \in \mathbb{N}}$ of real numbers is subadditive: $x_{m+n} \leq x_m + x_n$. Consider $L = \inf\limits_{n \in \mathbb{N}} \frac{x_n}{n}$. Either $L = - \infty$ and $\dfrac{a_n}{n}$ diverges properly to $-\infty$, or $$\lim_{n \to \infty} \frac{x_n}{n} = \inf_{n \in \mathbb{N}} \frac{x_n}{n} = L,$$ and in particular the limit exists.

Let $L = \inf\limits_{n \in \mathbb{N}} \frac{x_n}{n}$. The case $L = - \infty$ is easy, so assume $L \gt -\infty$. For $\varepsilon \gt 0$ there is an $m$ such that $\frac{x_m}{m} \lt L + \varepsilon$. Writing $n = km + r$ with $0 \leq r \lt m$ we get $$L \leq \frac{x_{n}}{n} \leq \frac{k \cdot x_m + x_r}{km+r} \leq \frac{x_m}{m}+ \frac{x_r}{n} \leq \frac{x_m}{m} + \frac{C}{n}$$ with $C = \max{\{x_0,\ldots,x_{m-1}\}}.$ For $n \geq C/\varepsilon$ we thus have $\displaystyle L \leq \frac{x_n}{n} \leq \frac{x_m}{m} + \varepsilon \leq L+2\varepsilon$ and thus the limit exists and equals the infimum of the sequence.

The second part is:

Suppose the sequence $(a_n)_{n \in \mathbb{N}}$ satisfies $-1 + a_m + a_n \leq a_{m+n} \leq 1 + a_m + a_n$. Then the limit $L = \lim\limits_{n \to \infty}\frac{a_{n}}{n}$ exists and $L-1 \leq \frac{a_{n}}{n} \leq L+1$.

Note that the sequence $b_n = 1+a_n$ is subadditive: $b_{m+n} \leq b_m + b_n$ hence we can apply the first part to it and find that $$-\infty \leq L = \inf_{n \in \mathbb{N}} \frac{1+a_{n}}{n} = \lim_{n \to \infty} \frac{1+a_{n}}{n} \lt \infty.$$ Similarly, $c_n = 1-a_n$ is subadditive and hence $$- \infty \leq -L = \inf_{n \in \mathbb{N}} \frac{1-a_n}{n} = \lim_{n\to\infty}\frac{1-a_n}{n} \lt \infty.$$ Therefore $L$ is a real number and $L \leq \dfrac{1+a_n}{n}$ together with $-L \leq \dfrac{1-a_n}{n}$ yields the desired estimates $nL - 1 \leq a_n \leq nL+1$ where $L = \lim_{n\to\infty}\frac{a_n}{n}$ also follollows from the above.

These lemmas have many applications. An easy variant of this is that a submultiplicative sequence of non-negative numbers, that is $a_{n+m} \leq a_n a_m$ has the property that $a_{n}^{1/n}$ converges. This can be used for the spectral radius formula in functional analysis.

Recently, quasi-subadditive sequences have received quite a bit of attention in guise of quasi-morphisms with significant applications in group theory, dynamical systems, symplectic geometry, and so on.

A beautiful elementary application is Norbert A'Campo's model of real numbers via almost additive maps $\varphi: \mathbb{Z} \to \mathbb{Z}$ (he calls them slopes), that is functions $\varphi$ satisfying $$\sup\limits_{m,n \in \mathbb{Z}}{|\varphi(m+n) - \varphi(m) - \varphi(n)|} \lt \infty$$ modulo a simple equivalence relation. The basic idea here is that any real number $r$ yields such a map by setting $\phi(n) = \lfloor rn \rfloor$. The paper is highly recommended, as it contains quite a few ingenious constructions and interesting historical remarks.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.