# Prove $\lim_{n\to\infty} \frac{a_n}{n}$ exists for positive sequence where $a_{n+m} \leq a_n + a_m$

Let $\{a_n\}_{n=1}^\infty$ be a positive sequence of real numbers such that $a_{n+m} \leq a_n + a_m.$ Prove that $\lim_{n\to\infty} \frac{a_n}{n}$ exists by showing that $\lim_{n\to\infty} \frac{a_n}{n} = \inf_{n \geq 1} \frac{a_n}{n}.$

A similar question has been posted previously, see Limit for sequence $a_{m+n}\leq a_m+a_n$ , and I have found that this is the general result of "Fekete's Subadditive Lemma" for sequences, but I am unhappy with the few proofs I've seen. Perhaps the clearest one I have found is http://web.mat.bham.ac.uk/R.W.Kaye/seqser/fekete.html , but this seems a bit tricky for what is expected on this qualifier question.

We are given a hint "treat $\liminf$ and $\limsup$ separately". Does anyone know of a more direct way to show that this limit exists?

The canon is the following: writing $m=qn+r$ with $q=q(m)$ and $r=r(m)\in[0,n)$, we have $$\frac{a_m}m=\frac{a_{qn+r}}{qn+r}\le\frac{qa_n+a_r}{qn+r}\to\frac{a_n}n$$ when $m\to\infty$, which implies that $$\limsup_{m\to\infty}\frac{a_m}m\le\inf_n\frac{a_n}n\le\liminf_{m\to\infty}\frac{a_m}m$$ (you have to think that $n$ is fixed when letting $m\to\infty$).

I am only aware of proofs that use or essentially use the liminf and limsup. One way to see why those proofs work is to notice that $$\frac{a_{m+n}}{m+n} \leq \frac{m}{m+n} \frac{a_m}{m} + \frac{n}{m+n} \frac{a_n}{n}.$$ So in effect, $a_n/n$ is bounded above by every "average" of the earlier terms. Now to prove the result, notice that $$\frac{a_{kn}}{kn} \leq \frac{a_k}{k},$$ and for any $k$, let $R(k) = \max_{m \leq k}a_m$. So for any $N = kn+r$, (e.g. $n = \lfloor N/k \rfloor$) $0 \leq r \leq k$, $$\frac{a_N}{N} \leq \frac{kn}{N} \frac{a_{kn}}{kn} + \frac{r}{N}\frac{a_r}{r} \leq 1 \cdot \frac{a_k}{k} + \frac{R}{N}.$$ Now for a fixed $k$, if you let $N \to \infty$, you have that $$\limsup_{N \to \infty} \frac{a_N}{N} \leq \frac{a_k}{k}.$$ Then taking a liminf with $k \to \infty$ will finish it off.

Let $$\epsilon > 0$$, and let $$\alpha$$ be the infimum of the sequence $$\{\frac {a_n} n\}$$. Let $$k$$ be such that $$\frac {a_k} k < \alpha + \frac{\epsilon}2$$. Define $$M$$ to be max$$\{a_1,\ldots,a_{k-1},a_k\}$$. Let $$p$$ be such that $$\frac M p < \frac {\epsilon} 2$$. Define $$N := max\{p,k+1\}$$.

Then for any $$m \geq N$$, we have $$\frac {a_m} m \leq \frac {a_{nk}} m + \frac {a_{m-nk}} m$$, where $$nk$$ is the largest multiple of $$k$$ less than $$m$$. Then $$1 \leq m-nk \leq k$$, so $$a_{m-nk} \leq M$$.

Thus, $$\frac {a_m} m \leq \frac {a_{nk}} m + \frac M m < \frac {a_{nk}} m + \frac {\epsilon} 2$$. We note that $$a_{nk} \leq na_k < nk(\alpha+\frac {\epsilon} 2)$$.

Thus we further have $$\frac {a_m} m < \frac {a_{nk}} m + \frac {\epsilon} 2 < \frac {nk(\alpha+\frac {\epsilon} 2)} m + \frac {\epsilon} 2 < \alpha+\frac {\epsilon} 2+\frac {\epsilon} 2$$ since $$\frac {nk} m < 1$$.

Therefore, $$\alpha - \epsilon < \frac {a_m} m < \alpha + \epsilon$$ for all $$m \geq N$$, so the sequence converges to its infimum by definition of convergence.

Proof inspired by the answer linked below to the same problem. They still used lim inf and lim sup, but I saw a way to adapt their solution such that you didn't have to. https://math.stackexchange.com/a/2556769/462116