# Sequence such that $x_{n+m} \geq x_n+x_m$, show that $(\frac{n}{x_n})$ converges (or not)

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 ?

• 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$ – Chady Dec 25 '20 at 23:56
• See en.wikipedia.org/wiki/Superadditivity for this version of Fekete's lemma. – kimchi lover Dec 26 '20 at 1:15
• Thank you, seems interesting ! – Chady Dec 26 '20 at 7:58
• 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. – 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$$
\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}
• 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$. – Paul Sinclair Dec 26 '20 at 19:47