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

Question

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?

Answer 1

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$).

Answer 2

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.

Answer 3

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