Processing math: 100%

Wednesday, October 23, 2013

Subadditivity, Limits and Lim Inf

Consider a sub-additive sequence a_n for n \geq 1, where sub-additivity is defined as follows :
a_{n+m} \leq a_n + a_m

Fekete's Lemma says that for any such sequence \lim_{n \rightarrow \infty} a_n/n = \lim \inf_{n \rightarrow \infty} a_n/n , which can be easily proved. The proof is as follows-

Let \lim \inf_{n \rightarrow \infty} a_n/n  = l. Therefore, \exists K s.t.
\left\vert \frac{a_K}{K} - l \right\vert = \epsilon/2

Now consider a large enough L such that \frac{a_r}{KL} < \epsilon/2, \forall  r < K. Thus, for every n \geq KL we can write n as n = Kq + r, where q \geq L and r<K. Therefore,

\begin{align} \frac{a_n}{n} & \leq \frac{q a_K}{Kq+r} + \frac{a_r}{Kq+r} \\                         & \leq \frac{q a_K}{Kq} + \frac{a_r}{Kq} \\                         & \leq \frac{a_K}{K} + \frac{a_r}{Kq} \\                         & \leq  l + \frac{\epsilon}{2} + \frac{\epsilon}{2}\\ \end{align}

Since this is true for all n > KL the limit exists and is equal to l. An alternate but similar proof is given here.



No comments:

Post a Comment