2
$\begingroup$

I have some problems with this, because this sequence could converge to some point, or goes to infinity, only this two possibilities, and really I don´t know how to prove that no other possibility can happen, that´s my problem. The sequence is such that exist a fixed positive constant C, such that for every m,n integers $ a_m + a_n < a_{m + n} + C $

prove that $ (a_n)/n $ converge to a point, or goes to infinity $

and some idea to prove in general that other of two possibilities can´t happen?

  • 0
    This is called **Fekete subadditive lemma**, see http://en.wikipedia.org/wiki/Subadditivity#Properties2011-08-12

2 Answers 2

3

Replacing $a_n$ by $a_n - C$ affects neither to the convergence nor to the limiting value of $a_{n} / n$. In this case, we have $a_{m} + a_{n} \leq a_{m+n},$ and this gives a simple lower bound for $a_{n} / n$, namely $a_1$. Now this shows that $s = \limsup_{n\to\infty} a_{n} / n$ is either $+\infty$ or a finite constant.

Note that we can find a subsequence $n_k$ such that $a_{n_k} / n_{k} \to s$. Now fix $k$ and write $n = q n_k + r$, where $q$ and $r$ are integers depending on both $n$ and $k$ such that $1 \leq r \leq n_k$. Then $ a_{n} \geq a_{qn_{k}} + a_{r} \geq q a_{n_{k}} + a_{r}.$ Dividing both sides by $n$ gives $ \frac{a_{n}}{n} \geq \frac{q a_{n_{k}} + a_{r}}{qn_{k} + r} = \frac{a_{n_{k}} + (a_{r} / q)}{n_{k} + (r/q)}$ for $n$ large so that $q > 0$. Then taking $\liminf_{n\to\infty}$ to both sides yields $ \liminf_{n\to\infty} \frac{a_{n}}{n} \geq \frac{a_{n_{k}}}{n_{k}}.$ But since this is true for any $k$, taking $k \to \infty$ proves that $a_{n} / n$ tends to either $+\infty$ or a finite value as $n \to \infty$.

0

Try the below method:change variables $b_n=C-a_n$,we get $b_{n+m}.Besides,it is easily seen that $\{ \frac{a_n}{n}\}$ and $\{\frac{b_n}{n}\}$ have the same convergent behavoir(both are convergent to some point,or both go to infinity,or both are divergent).The convergence of $\{\frac{b_n}{n}\}$ is a well known result.You can do it on your own or see as follows:let $b=\lim_{n\longrightarrow \infty}\inf_{k>n}\{ \frac{b_k}{k}\}$,$b$ exsits (may be infinity).Similiarly,we have b'=\lim_{n\longrightarrow \infty}\sup_{k>n}\{ \frac{b_k}{k}\},and b\leq b'.Next we show that b=b'.By definition of $b$, \forall \epsilon >0,\exists N,s.t.|\frac{b_N}{N}-b|<\epsilon.By definition of b',there is a subsequnce $\{\frac{b_{n_r}}{n_r}\}$ which converges to b'.Note $\forall n_r,\exists k_r,q_r\in \mathbb{N}(0\leq q_r .Beside $b_{n_r}.Note $\{b_{q_r}\},\{q_r\}$ are bounded,thus taking limits with respect to $r$ in $\frac{b_{n_r}}{n_r}<\frac{k_r b_N+b_{q_r}}{k_r N+q_r}$,we get b'\leq \frac{b_N}{N}.Since $\epsilon $ is arbitary,we get b'\leq b.As a result,$b=b'$,which exactly means that the sequence $\{\frac{b_n}{n}\}$ converges.As it it unknown whether $b$ is finite or infinite,we get the two cases you have just pointed out.

  • 0
    @sos440:nothing serious:)2011-08-12