Let $(x_n)$ be a sequence such that $x_n \geq 0$ $\forall n \in \mathbb N$ and that $$x_{n+m} \geq x_n+x_m \quad \forall n,m \in \mathbb N^* $$ I have the feeling that $(\frac{n}{x_n})$ converges but I have a little problem with the proof's end. Can someone help me (the statement can also be wrong but I do not find counterexamples) ?

We have $x_{n+m} \geq x_n+x_m \quad \forall n,m \in \mathbb N^*$, we want to show that $(\frac{n}{x_n})$ converges :

Let's show that $ \lim_{n\to\infty} \frac{n}{x_n} = a$ where $a = inf\{\frac{n}{x_n} | n \in \mathbb N^*\}$ :

We have that $x_{pq+r} \geq x_{pq}+x_r \geq px_q+x_r$ with $p,q,r \in \mathbb N^*$ that gives $\frac{1}{x_{pq+r}} \leq \frac{1}{px_q+x_r}$.

Let $\epsilon > 0$, as $a$ is an inf, we have that $\exists q \in \mathbb N^*$ such that $ a \leq \frac{q}{x_q} \leq a + \frac{\epsilon}{2} $

Let $N>q$, so we have for $n > N$ and by Euclidean division on $n$, $$a \leq \frac{n}{x_n} \leq \frac{pq+r}{px_q+x_r} = \frac{pq}{px_q+x_r}+\frac{r}{px_q+x_r} \leq \frac{q}{x_q} + \frac{q}{px_q+x_r} \leq \frac{q}{x_q} + \frac{q}{px_q} = (1+\frac{1}{p})\frac{q}{x_q} \leq 2 \frac{q}{x_q} $$ Now I can write $a \leq \frac{n}{x_n}\leq 2a+\epsilon$ but we want $a \leq \frac{n}{x_n}\leq a+\epsilon$, is there a way to fix it ?

  • $\begingroup$ Also like to add that $x_n$ is increasing since $x_{n+1} \geq x_n + x_1 \implies x_{n+1} - x_n \geq x_1 \geq 0$ $\endgroup$ – Chady Dec 25 '20 at 23:56
  • 4
    $\begingroup$ See en.wikipedia.org/wiki/Superadditivity for this version of Fekete's lemma. $\endgroup$ – kimchi lover Dec 26 '20 at 1:15
  • $\begingroup$ Thank you, seems interesting ! $\endgroup$ – Chady Dec 26 '20 at 7:58
  • 2
    $\begingroup$ Note that the $0$ sequence satisfies the conditions, but $\left(\frac n{x_n}\right)$ is undefined at every index. So there there is at least one exception. $\endgroup$ – Paul Sinclair Dec 26 '20 at 16:31

Instead of $N > q$, pick $N >q\left(2+\dfrac{2a}\epsilon\right)$. If $n > N$, then $$p > \dfrac nq - 1 > 1 + \dfrac {2a}\epsilon\\ p\dfrac \epsilon 2 > \dfrac \epsilon 2 + a\\\dfrac \epsilon 2 > \dfrac{a + \frac \epsilon 2}p$$

From your calculation,

$$\begin{align}a \le \dfrac n{x_n} &\le \left(1 + \dfrac1p \right)\dfrac q{x_q} \\&\le \left(1 + \dfrac1p\right)\left(a + \dfrac \epsilon 2\right)\\ &\le a + \dfrac \epsilon 2 + \dfrac{a + \frac \epsilon 2}p\\&\le a + \dfrac \epsilon 2 + \dfrac \epsilon 2\end{align}$$

  • $\begingroup$ Thank you ! Quite technical but I checked steps 1 by 1 and seems all good ! $\endgroup$ – Chady Dec 26 '20 at 18:49
  • $\begingroup$ The trick was recognizing that your replacing $1 +\frac 1p$ with $2$ was an unneccesary over estimation. For high $p$ (equivalently, high $n$) $1+\frac 1p$ is barely over $1$. The rest was just a little algebra to figure out what it would take to get the remainder $\frac 1p\left(a + \frac \epsilon 2\right)$ to be less than the needed $\frac\epsilon 2$. $\endgroup$ – Paul Sinclair Dec 26 '20 at 19:47

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.