8
$\begingroup$

Given a positive sequence $x_1 , x_2 , ...$ such that $x_{m+n} \ge x_m + x_n \forall m,n \in N$

Prove that $\frac{x_n}{n} \to l $ where $l$ may be a number or infinity.

Here's my original approach:

It is easy to prove that $\displaystyle \frac{x_1}{1} \le \frac{x_2}{2} \le \frac{x_4}{4} \le ...$ so the sequence $\frac{x_{2^n}}{2^n}$ has a limit c (*) (i'm supposing $\frac{x_n}{n}$ is bounded). So it is sufficient to prove that for any fixed odd number d, the sequence $\frac{x_{d.2^n}}{d.2^n}$ has a limit c too.

Any number d can be represented as $\displaystyle d=2^{e_1} + 2^{e_2} + ... + 2^{e_k}$ So $\frac{x_{d.2^n}}{d.2^n} \ge \frac{x_{2^{e_1 + n}} + x_{2^{e_2 + n}} + ... + x_{2^{e_k + n}}}{d.2^n}$ It is easy to check that the right side of this ineq tends to c using (*).

Similarly, d can also be represented as $\displaystyle d+2^{f_1} + 2^{f_2} + ... + 2^{f_t} = 2^g$ so $\frac{x_{d.2^n}}{d.2^n} \le \frac{x_{2^{g+n}}-x_{2^{f_1+n}} - x_{2^{f_2+n}} - ... - x_{2^{f_t+n}}}{d.2^n} $. Again, from (*) one can check that the right side tends to c when n tends to infinity.

Thus the proof is complete. This proof looks suspicious, so I would be glad if someone can help me verify it. Thank you.

EDIT: The proof is wrong, as pointed out in one of the answer below.

$\endgroup$
  • 3
    $\begingroup$ Actually I have been able to give a proof, but it's not a nice one. I'm interested in other proofs, and to not let my proof influence yours, I don't post it here. $\endgroup$ – tom_a2 Mar 26 '13 at 4:34
  • 2
    $\begingroup$ By replacing $x_n$ by $-x_n$, we may assume $(x_n)$ is subadditive. Then the claim reduces to the Fekete's Subadditive Lemma. Googling with this title may give you various proofs. $\endgroup$ – Sangchul Lee Mar 26 '13 at 5:01
  • 2
    $\begingroup$ The second comment is the perfect reply to the passive-aggressive "what have you tried" queries that plague this web site. Well done. $\endgroup$ – zyx Mar 26 '13 at 5:27
  • 2
    $\begingroup$ @tom_a2 Ah, OK. It might be better next time to write that in the question, though. $\endgroup$ – Avi Steiner Mar 26 '13 at 12:37
  • 2
    $\begingroup$ @AviSteiner, you requested some material from the the OP (whatever he had "tried"), which he posted on the same day, with a personal notification to you. Doesn't the request for such material incur some obligation to respond when it is delivered? I hope it was not just an enforcement ritual about "community standards" and that you actually intended to engage with the poster and the material provided. There is a trend of snarky "What Have You Tried" postings on the site and they very often seem to be made carelessly. $\endgroup$ – zyx Apr 5 '13 at 23:37
2
$\begingroup$

The sequence of ratios $r_n = \frac{x_n}{n}$ has its growth limited only from below (considering any term compared to the earlier ones, and building the sequence step by step), so it could certainly go to +infinity.

The case of interest is what happens when $r_n$ is bounded above. Let $L$ and $U$ be the lim inf and lim sup of the ratios as $n$ goes to infinity. Translated to the ratios, the inequality on the sequence is $r_{m+n} \geq \frac{mr_m + nr_n}{m+n}$. Letting $m=kp$ and $0 \leq n < p$ for large $k$ (going to infinity) and $p$ constant, this means that $r_p$ is a lower bound on $L$ for any $p$. That implies that $L \geq U$ and therefore $L=U$.

The argument did not need a separate case for $U = +\infty$, but that was not obvious before writing it.

$\endgroup$
  • $\begingroup$ To go from the inequality to $r_p$ as lower bound, I am assuming the same inequality written for several arguments, $r_{a+b+c+d+\dots} \geq$ (the analogous expression in several variables). Then take $k$ of the variables equal to $p$ and one more variable equal to $n$. Or use the inequality with $m,n$ only and show by induction on $k$ that $r_{kp} \geq r_p$ for all $k$ and $p$. $\endgroup$ – zyx Mar 26 '13 at 8:57
  • $\begingroup$ Excellent solution, that's what I've been looking for. Also, I have posted my original solution. $\endgroup$ – tom_a2 Mar 26 '13 at 16:17
5
$\begingroup$

See here. Fekete's superadditive lemma says that $$\lim_{n\to\infty}\frac{x_n}{n}=\sup_{n\in\mathbb N}\frac{x_n}{n}.$$

$\endgroup$
  • $\begingroup$ Thank you that's a good reference. $\endgroup$ – tom_a2 Mar 26 '13 at 16:24
4
$\begingroup$

An answer dealing with the first version of the question is now accepted hence the OP might or might not still be looking for an answer to the second version of their post, which asks to check a proof. Anyway, here is a take on that question: is the proposed proof correct?

It is easy to prove that $\frac{x_1}{1} \le \frac{x_2}{2} \le \frac{x_4}{4} \le ...$ so the sequence $\frac{x_{2^n}}{2^n}$ has a limit $c$ (*) (i'm supposing $\frac{x_n}{n}$ is bounded).

One should not have to assume that the sequence of general term $x_n/n$ is bounded, or, at least, one should treat this case and then the case when it is unbounded. Anyway, for now, let us assume that this sequence is bounded.

So it is sufficient to prove that for any fixed odd number $d$, the sequence $\frac{x_{d.2^n}}{d.2^n}$ has a limit $c$ too.

Sorry? This would be sufficient if the claim below were true.

Claim: Let $(a(n))_n$ denote a bounded sequence such that, for every odd $k$, the sequence $(a(k2^n))_n$ converges to the same limit $c$. Then the whole sequence $(a(n))_n$ converges to $c$.

The claim is not true. To see why, assume that, for every $n$ and every odd $k$, $a(k2^n)=c'$ if $n\leqslant k$ and $a(k2^n)=c$ if $n\gt k$. Then the sequence $(a(n))_n$ fits the hypotheses of the claim and $a(k2^k)=c'$ for every odd $k$. Since the set $\{k2^k\mid k\ \text{odd}\}$ is unbounded, if $c\ne c'$, the sequence $(a(n))_n$ does not converge to $c$ (and in fact this sequence diverges).

Hence at least this step of the proof needs to be modified.

Edit: The negative result above has a, slightly loose but perhaps more familiar, analogue, which goes as follows. Consider the doubly-indexed sequence $(x(k,n))_{k,n}$ defined by $x(n,k)=1$ if $n\lt k$ and by $x(n,k)=0$ if $n\geqslant k$. Then $\lim\limits_{n\to\infty}x(n,k)=0$ for each $k$ while $\lim\limits_{k\to\infty}x(n,k)=1$ for each $n$.

$\endgroup$
  • $\begingroup$ I just noticed this addition to the thread. +1 for an actually constructive contribution, different from (if not quite cancelling) the commentary on the meta.MSE. $\endgroup$ – zyx Apr 6 '13 at 12:31
  • $\begingroup$ You're right, I've made a careless mistake... It is sometimes hard for one to recognize flaws in his own arguments; that's one reason why sites like this are helpful to learners like me. $\endgroup$ – tom_a2 Apr 6 '13 at 16:23
  • $\begingroup$ @zyx You know what? Your approval is not something I care a lot about (and I missed that you were appointed to give classroom-style rewards on MSE, were you?). Surely you will continue to (try to) intimidate people on the meta site, but whether you do or not, I suggest that you abstain from commenting on my answers on the main site unless you have some mathematical input to provide (which is not the case here). $\endgroup$ – Did Apr 6 '13 at 16:47
  • $\begingroup$ @tom_a2 Please do not feel concerned by my previous comment, you are not (it addresses objectionable behaviour by another user on the meta site, hence you have nothing to be concerned about). More interestingly... yes, the mistake in your "proof" is a tempting one since one may have the impression the full sequence is so constrained by the condition that all these subsequences converge to the same limit, that it must converges itself--but not so. I added an analogous example, tell me if this helped. $\endgroup$ – Did Apr 6 '13 at 16:48
  • $\begingroup$ @Did, if you view the extremely common "+1 for (reason)" commented upvotes as the dubious largesse of self-appointed classroom reward donors, that would be a novel idea to contribute to the meta, but I don't share it. Assuming that this history of "intimidating people on the meta" might be more than just your personal invention, I can't think of a better way to protect the community, or at least your own credibility, than by providing a link to a comment or answer where such intimidation attempts actually occurred. You know, something that others can verify. $\endgroup$ – zyx Apr 8 '13 at 1:05
0
$\begingroup$

Personally, it is geometrically clear yet I am not sure how to write it algebraically. Consider the real-valued function $f(x)$ with the property $f(x+y)\geqslant f(x)+f(y)$. Then $f(x)$ is concave up and with the lower bound $y=f(1)x$, and $\frac{f(a)}{a}$ is non-decreasing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.