Homework Help: Prove that the limit exists

1. Jan 21, 2012

hrach87

1. The problem statement, all variables and given/known data
It is given the sequence $a_{n}$, where $a_{n}>0$ and $a_{n+m}\leq a_{n}+a_{m}$

2. Relevant equations
Prove that the limit $lim_{n\rightarrow \infty} \frac{a_{n}}{n}$ exists.

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

2. Jan 21, 2012

tiny-tim

welcome to pf!

hi hrach87! welcome to pf!
so an/n is bounded

carry on from there!

3. Jan 22, 2012

Dick

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

4. Jan 22, 2012

poochie_d

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.

5. Jan 22, 2012

Dick

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.

Last edited: Jan 22, 2012
6. Jan 23, 2012

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 :)

7. Jan 23, 2012

Dick

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

8. Jan 23, 2012

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!

9. Jan 23, 2012

Dick

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.

Last edited: Jan 23, 2012
10. Jan 26, 2012

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.

11. Jan 26, 2012

Dick

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

12. Jan 27, 2012

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$

Last edited: Jan 27, 2012
13. Jan 27, 2012

Dick

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?

14. Jan 29, 2012

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