Prove that lim=inf

[MM]

Let [tex]\{a_{n}\}_{n\ge1}[/tex] be a sequence, such that [tex]a_{n}\ge 0[/tex] [tex]\forall n[/tex]. We also know that [tex]a_{m+n}\le a_m+a_n[/tex] [tex]\forall m,n[/tex]. Prove that [tex]\lim_{n\to \infty} \frac{a_n}{n}=\inf\{\frac{a_n}{n}| n\in \mathbb{N}\}[/tex].

[Guest]

First show that for any given [tex]s[/tex] and, [tex]\epsilon >0[/tex] there exists [tex]N(s,\epsilon)[/tex] such that
[tex]\frac{a_t}{t}\leq \frac{a_s}{s}+\epsilon[/tex]
holds for all [tex]t\geq N(s,t)[/tex]. (This shows that [tex]\{\frac{a_n}{n}\}_{n\geq 1}[/tex] is almost a decreasing sequence but not quite.)

To prove this statement observe that
[tex]a_t\leq \lfloor\frac{t}{s}\rfloor a_s+a_r[/tex]
where [tex]r[/tex] is the remainder of [tex]t[/tex] divided by [tex]s[/tex] (this follows from the fact that [tex]a_{m+n}\leq a_m+a_n \forall m,n[/tex] and [tex]t = \lfloor\frac{t}{s}\rfloor s+r[/tex]). Consequently we know that
[tex]a_t\leq (\frac{t}{s}) a_s+a_r[/tex]
and so
[tex]\frac{a_t}{t}\leq \frac{a_s}{s}+\frac{a_r}{t}[/tex].
It is easy to see that [tex]a_r/t[/tex] vanishes to 0 as [tex]t[/tex] increases proving our claim.

Let [tex]l[/tex] be the infimum of [tex]\frac{a_n}{n}[/tex] (recall the infimum always exists when working in the reals). To prove the limit of the sequence exists and that it converges to [tex]l[/tex] it is enough to show that for any given [tex]\epsilon>0[/tex] there exists some [tex]N'(\epsilon)[/tex] such that for all [tex]n\geq N'[/tex] we have
[tex]l\leq \frac{a_n}{n}\leq l+2\epsilon[/tex].

Clearly [tex]l\leq \frac{a_n}{n}[/tex] holds for all [tex]n[/tex] by the definition of the infimum.

By the definition of the infimum we know there exists some [tex]s[/tex] such that [tex]\frac{a_s}{s}\leq l+\epsilon[/tex]. By our earlier claim we know that when [tex]n[/tex] is sufficiently large we have [tex]\frac{a_n}{n}\leq \frac{a_s}{s}+\epsilon[/tex]. Combining these two facts gives us [tex]\frac{a_n}{n}\leq l+2\epsilon[/tex] as required.

Hope this helps,

R. Baber.

[MM]

Actually, I know the solution. I just posted it, so that someone tries to solves it just for pleasure!