Existence of Limit for Positive Sequence

[hrach87]

Homework Statement

It is given the sequence a_{n}, where a_{n}>0 and a_{n+m}\leq a_{n}+a_{m}

Homework Equations

Prove that the limit lim_{n\rightarrow \infty} \frac{a_{n}}{n} exists.

The Attempt at a Solution

I have shown that a_{n}\leq n a_{1}. From the last inequality I obtain that \sqrt[n]{a_{1} a_{2} ... a{n}}\leq n! a_{1}^{n}. But don't know are this steps useful?

 

[tiny-tim]

welcome to pf!

hi hrach87! welcome to pf!

I have shown that a_{n}\leq n a_{1}.

so a_n/n is bounded …

carry on from there! ​

 

[Dick]

It would be nice now if you could show an/n is decreasing.

 

[poochie_d]

It would be nice now if you could show an/n is decreasing.

The sequence is not necessarily decreasing:
e.g. a_n = n satisfies the given conditions but \frac{a_n}{n} = 1 is nondecreasing.

I think it would be be more helpful to show that \frac{a_n}{n} is a Cauchy sequence, since being Cauchy is equivalent to being convergent for real sequences.

 

[Dick]

The sequence is not necessarily decreasing:
e.g. a_n = n satisfies the given conditions but \frac{a_n}{n} = 1 is nondecreasing.

I think it would be be more helpful to show that \frac{a_n}{n} is a Cauchy sequence, since being Cauchy is equivalent to being convergent for real sequences.

I should have said 'nonincreasing' i.e. \frac{a_n}{n} \le \frac{a_m}{m}, n \gt m. Since \frac{a_n}{n} is bounded below by 0, that's enough to show that it converges.

 

[hrach87]

It is obvious that the limit exists if \frac{a_n}{n} is nonincreasing, but I can't prove that sequence \frac{a_n}{n} is nonincreasing... The problem is to show the last one :)

 

[Dick]

It is obvious that the limit exists if \frac{a_n}{n} is nonincreasing, but I can't prove that sequence \frac{a_n}{n} is nonincreasing... The problem is to show the last one :)

Try and write a relation between \frac{a_n}{n}, \frac{a_m}{m} and \frac{a_{m+n}}{m+n}.

 

[poochie_d]

You won't be able to prove this by showing that the sequence is nonincreasing/nondecreasing, since you can find contrary examples satisfying the given conditions.

Consider, for instance, the sequence a_n where a_n = n + 1 if n is odd, and a_n = n if n is even. (So the terms of the sequence will be 2,2,4,4,6,6,8,8,...) Then it satisfies a_{n+m} \leq a_n + a_m (easy to check), but \frac{a_n}{n} = 1 + \frac{1}{n} for n odd, and \frac{a_n}{n} = 1 for n even, which is neither nondecreasing nor nonincreasing.

I think your problem may not be so trivial as it seems. I can think of three possible ways of approaching it:
1) Show that \frac{a_n}{n} is Cauchy
2) Show that the lim sup and the lim inf are the same (following Dick's advice to some extent)
(The above two might involve induction.)
3) Consider instead the function f with f(x) > 0 and f(x+y) \leq f(x) + f(y), then prove it for \frac{f(x)}{x} using the tools of calculus (somehow)

There are probably other ways of doing this, but I can't really think of any (sorry, it has been a while since I took calculus). I hope this helps. Good luck!

 

[Dick]

You won't be able to prove this by showing that the sequence is nonincreasing/nondecreasing, since you can find contrary examples satisfying the given conditions.

Consider, for instance, the sequence a_n where a_n = n + 1 if n is odd, and a_n = n if n is even. (So the terms of the sequence will be 2,2,4,4,6,6,8,8,...) Then it satisfies a_{n+m} \leq a_n + a_m (easy to check), but \frac{a_n}{n} = 1 + \frac{1}{n} for n odd, and \frac{a_n}{n} = 1 for n even, which is neither nondecreasing nor nonincreasing.

I think your problem may not be so trivial as it seems. I can think of three possible ways of approaching it:
1) Show that \frac{a_n}{n} is Cauchy
2) Show that the lim sup and the lim inf are the same (following Dick's advice to some extent)
(The above two might involve induction.)
3) Consider instead the function f with f(x) > 0 and f(x+y) \leq f(x) + f(y), then prove it for \frac{f(x)}{x} using the tools of calculus (somehow)

There are probably other ways of doing this, but I can't really think of any (sorry, it has been a while since I took calculus). I hope this helps. Good luck!

Ooo. You are so right. Nice example. Here's something I did manage to prove. If we define b_n=\frac{a_n}{n} then you can show \frac{b_1}{n}+b_{n-1} \frac{n-1}{n} \ge b_n. That 'almost' says that the b's are nonincreasing. Hmm. Better think about this some more.

 

[hrach87]

I have already understood that the sequence \frac{a_{n}}{n} can not be non-increasing. I have found some way to solve this problem. I have already shown that the sequence a_{n} is bounded, so I can take from that sequence a sub-sequence, say a_{n_k}, having limit a. If you can help me to show that I can consider that \frac{n_{k+1}}{n_{k}}\rightarrow 1, than I can solve the problem.

 

[Dick]

I have already understood that the sequence \frac{a_{n}}{n} can not be non-increasing. I have found some way to solve this problem. I have already shown that the sequence a_{n} is bounded, so I can take from that sequence a sub-sequence, say a_{n_k}, having limit a. If you can help me to show that I can consider that \frac{n_{k+1}}{n_{k}}\rightarrow 1, than I can solve the problem.

I don't think that's going to work. A sequence like a_n=2^{-n} works as well.

 

[hrach87]

I found the solution of my problem.

Denote a=inf\{\frac{a_{n}}{n}\}. a is finite, because the set \{\frac{a_{n}}{n}\} is bounded (a\ge 0). For every \epsilon>0 exists a natural number n_{0}, such that \frac{a_{n_{0}}}{n_{0}}<\epsilon.
Let us fix the number n_{0}.
Every n\in {N} we can introduce by this way: n=kn_{0}+p, where k,p\in{N} and p\in\{0, 1, ..., n_{0}-1\}. So we obtain
\frac{a_{n}}{n}=\frac{a_{kn_{0}+p}}{n}\le \frac{a_{kn_{0}}+a_{p}}{n}\le \frac{ka_{n_{0}}}{n}+\frac{a_p}{n}\le \frac{a_{n_{0}}}{n_{0}}+\frac{pa_{1}}{n}<\epsilon+\frac{a_{1}n_{0}}{n}.
For the same \epsilon if we take n^{'}\ge \frac{a_{1}n_{0}}{\epsilon}, than for every n>n^{'} we have \frac{a_{1}n_{0}}{n}<\epsilon.
Finally, we obtain that for every \epsilon>0 exists a natural n^{'}, such that for every n>n^{'} a\le \frac{a_{n}}{n}<a+2\epsilon, so
lim_{n\rightarrow \infty}\frac{a_{n}}{n}=a

 

[Dick]

I found the solution of my problem.

Denote a=inf\{\frac{a_{n}}{n}\}. a is finite, because the set \{\frac{a_{n}}{n}\} is bounded (a\ge 0). For every \epsilon>0 exists a natural number n_{0}, such that \frac{a_{n_{0}}}{n_{0}}<\epsilon.
Let us fix the number n_{0}.
Every n\in {N} we can introduce by this way: n=kn_{0}+p, where k,p\in{N} and p\in\{0, 1, ..., n_{0}-1\}. So we obtain
\frac{a_{n}}{n}=\frac{a_{kn_{0}+p}}{n}\le \frac{a_{kn_{0}}+a_{p}}{n}\le \frac{ka_{n_{0}}}{n}+\frac{a_p}{n}\le \frac{a_{n_{0}}}{n_{0}}+\frac{pa_{1}}{n}<\epsilon+\frac{a_{1}n_{0}}{n}.
For the same \epsilon if we take n^{'}\ge \frac{a_{1}n_{0}}{\epsilon}, than for every n>n^{'} we have \frac{a_{1}n_{0}}{n}<\epsilon.
Finally, we obtain that for every \epsilon>0 exists a natural n^{'}, such that for every n>n^{'} a\le \frac{a_{n}}{n}<a+2\epsilon, so
lim_{n\rightarrow \infty}\frac{a_{n}}{n}=a

I guess that's ok. I still might have to read it a few more times. But you want to start with a\le \frac{a_{n_0}}{n_0}<a+\epsilon, not \frac{a_{n_{0}}}{n_{0}}<\epsilon, right?

 

[hrach87]

Of course, that's my careless mistake. It is obvious that from the definition of infimum we have that for every \epsilon>0 exists a natural number n_{0} such that \frac{a_{n_{0}}}{n_{0}}<a+\epsilon.