Let $(x_n)_{n \ge 1}$ be a sequence of real numbers satisfying

$$x_{m+n} \le x_n+x_m$$

$m,n \ge 1$. Show that $\lim \limits_{n \to \infty} \dfrac{x_n}{n}$ exists and is equal to $\inf \left \{\dfrac{x_n}{n}; n\ge 1 \right \}$.

  • 2
    $\begingroup$ Are you sure this is the question? What about $x_n = 2^n$? Is it actually $x_{m+n} \le x_n + x_m$? $\endgroup$ – A.S Apr 4 '13 at 2:01
  • $\begingroup$ May I suggest that you change the title for a more explicit one? $\endgroup$ – Julien Apr 4 '13 at 2:54
  • 1
    $\begingroup$ A proof of Fekete's lemma (together with some references and related facts) is also given in an answer to this question: math.stackexchange.com/questions/57455/… $\endgroup$ – Martin Sleziak Apr 19 '14 at 21:28

This was false with the reverse inequality. Take $x_n=n^2$, for instance. It would still have been true with $\sup$ instead of $\inf$, as it follows from the following.

Now it is true: if $x_n$ is subadditive, i.e. $$ x_{n+m}\leq x_n+x_m\qquad\forall n,m\geq 1 $$ then $\lim \frac{x_n}{n}=\inf \frac{x_n}{n}$. Note that moreover this limit/inf can take any value in $[-\infty,+\infty)$. To see why the case $-\infty$ can occur, take $x_n=-n^2$. For real values, take $x_n=an$.

This is called Fekete's lemma. See here for a proof by one of our colleagues. The strategy is to prove that $$ \inf \frac{x_n}{n}\leq \liminf \frac{x_n}{n}\leq\limsup\frac{x_n}{n}\leq\frac{x_k}{k}\qquad\forall k\geq 1. $$ The first two inequalities are trivial. The last one follows from a neat application of the Euclidean division. Then take the inf on the rhs to see that all these quantities are equal. So $\frac{x_n}{n}$ tends to $\inf \frac{x_n}{n}$. This is in $[-\infty,\infty)$. As observed earlier, all these cases can occur. Only the case $+\infty$ must be excluded, as the inf of a nonempty set is $<+\infty$.

Note: taking the exponential, you get a similar statement for submultiplicative positive sequences. A famous application of this is the fact that $\|a^n\|^\frac{1}{n}$ converges for every element $a$ in a Banach algebra. With more work, one can show that the limit is the spectral radius of $a$. That's called the spectral radius formula.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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