13
$\begingroup$

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.

  • 2
    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ő](http://books.google.com/books?id=b9l2NqGEFzg), Exer. 98/99, by the way. (they attribute it to Fekete).2011-08-14
  • 0
    thanks man, but i did not understood why L equals the inf of this set , and also , can you give me the name of the book please?2011-08-14
  • 1
    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](http://books.google.com/books?id=b9l2NqGEFzgC&pg=PA198)*. 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.2011-08-14
  • 1
    @Theo: Wikipedia has a reference (found on [Subadditivity](http://en.wikipedia.org/wiki/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.2011-08-14
  • 1
    @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... :)2011-08-14
  • 0
    Sorry for my stupid questions, but I don´t understand only one thing, I know that $ a_n / n $ must converges, obviously your $ b_n / n $ also , but why that limit L must be lower than the inf of that sequence <.2011-08-14
  • 0
    If you cancel the fraction $\dfrac{l_k}{nl_k+r_k}$ with $l_k$ and then let $k \to \infty$ you get $L$ on the left hand side and $\frac{a_n}{n}$ on the right hand side. Note that $a_{r_k} \in \{ a_{0}, \ldots,a_{n-1}\} \leq C$ and $0 \leq r_k/l_k$, so the right hand side can be estimated by $\frac{1}{n} a_{n} + \frac{C}{m_k}$. Now let $k \to \infty$.2011-08-14
  • 0
    Ok, sorry for my stupid questions, I got it everything2011-08-14
  • 2
    @Daniel: Please don't use subjective titles like "It's difficult", "it's hard", etc.2011-08-14
  • 1
    Daniel, come on! No need to feel bad, it's not trivial at all! (I assure you that I spent hours pondering this exercise when I first saw it). I've seen quite a few serious research papers (some from the past 10 years) still giving references for that fact (this rarely happens when people are talking about sequences or series).2011-08-14

1 Answers 1

16

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.