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