5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.