# Sequence Limit Problem: If $0 \leq x_{m+n} \leq x_n + x_m$ then limit of $x_n/n$ exists

If the sequence $\{x_n\}$ satisfies the property that $0 \leq x_{m+n} \leq x_n + x_m$ for all $n$, $m \in \mathbb{N}$ , show that the limit of the sequence $\left\{\frac{x_n}{n}\right\}_n$ exists. Provide an example of such a sequence.

I can show that it is bounded, but I don't know how to show that it is monotone increasing (I think it is monotone increasing, not sure).

Let's fix the number $p$ and write $n = pm + k$, where $0 \leq k < p$, then we have

\begin{align} \frac{x_{pm+k}}{pm+k} &\leq \frac{x_{pm}}{pm+k} + \frac{x_k}{pm+k} \\ & \leq \frac{mx_p}{pm} + \frac{px_1}{pm} \end{align}

when we send $m$ to infinity, we get $\limsup\frac{x_n}{n} \leq \frac{x_p}{p}$, since here $k$ can only vary finitely from 0 to $p-1$

Since $p$ is arbitrary, we can say that $\exists N_1$, such that for all $n \geq N_1$, $\frac{x_n}{n} \leq \frac{x_1}{1}$.

and $\exists N_2$, such that for all $n \geq N_2$, $\frac{x_n}{n} \leq \frac{x_{N_1}}{N_1}$

continue in this way, the sequence $\frac{x_{N_k}}{N_k}, k = 1,2,\cdots$ is decreasing and bounded for below by 0, so their limit exsits.

And the conclusion follows by $\limsup\frac{x_n}{n} \leq \frac{x_p}{p}$ for any $p$.

Or as Zarrax says in the comment, we can directly conclude by noting $\limsup\frac{x_n}{n} \leq \liminf\frac{x_p}{p}$

One example is to take $a_n = \sqrt{n}$

• Aren't you already done once you know that $\limsup {a_n \over n} \leq {a_p \over p}$ for all $p$? Once you know that, you automatically have $\limsup {a_n \over n} \leq \liminf {a_p \over p}$ so the limit must exist. – Zarrax Apr 19 '14 at 15:19
• Yeah, you are right, this makes the proof shorter, thanks – Petite Etincelle Apr 19 '14 at 15:23
• just wondering must the sequence be non-negative? From the proof, i think it doesn't really matter right? does it? – user10024395 Apr 20 '14 at 3:42
• @user136266 if the sequence is not bounded from below, its limit can be $-\infty$, take $x_n = -n$ for example – Petite Etincelle Apr 20 '14 at 8:21