Let 0 < xn ↗ ∞ such that xn+1 - xn → 0 as n → ∞ . Then, for every 0 < c < 1, there exists a subsequence k(n) such that xk(n) - xn → c as n → ∞ .
Is the problem true if c ≥ 1?
I was thinking of defining k(n) := sup { k ≥ n : xk - xn < c }. Then
xk(n) - xn < c ≤ xk(n)+1 - xn ,
and the length of the interval containing c is xk(n)+1 - xk(n) , which → 0 as n → ∞ by hypothesis.
Is this OK for all c > 0, or I am missing something?
Let xn=ln(n+1).
Since lnx is strictly increasing and n+1>1, then ln(n+1)>ln1=0, thus xn>0.
Further, since lnx tends to infinity as x tends to infinity, then ln(n+1) tends to infinity as n tends to infinity, i.e. xn diverges to infinity.
Also, xn+1-xn= ln(n+2)- ln(n+1)=ln((n+2)\(n+1)), and since (n+2)\(n+1) tends to 1 as n tends to infinity, then ln((n+2)\(n+1)) tends to ln1=0, and thus xn+1-xn tends to 0 as n tends to infinity.
Further, let (yn) be a strictly increasing sequence of natural numbers.
Then xyn is a subsequence of xn, and xyn-xn= ln(yn+1)- ln(n+1)=ln((yn+1)\(n+1)).
Choosing yn=mn, where m is a natural number at least 3, we have that (yn) is a strictly increasing sequence of natural numbers and xyn-xn= ln((mn+1)\(n+1)).
As n tends to infinity, the sequence (mn+1)\(n+1) tends to m, and thus xyn-xn tends to lnm, which is greater than 1, as m is at least 3.
To include 1 in the limits of xyn-xn, we may divide the initial sequence by ln3, i.e.
we may consider the sequence xn=ln(n+1)\ln3.
The new sequence has strictly positive terms, diverges to infinity, it still has the property that xn+1-xn tends to 0, and if yn=mn, then xyn-xn tends to lnm\ln3, which is 1 if m=3, and >1 if m>3.
Dear George Stoica
If we consider
xn = n + 1/n, k(n ) = n+c, c ∈ N.
xk(n) = n + c + 1/(n+c)
xk(n) is a subsequence of xn .
Lim ( xk(n) - xn ) = c.
Best regards
Yes, dear Issam Kaddoura , but you have given just an example. I think that George's problem is to prove the existence of the subsequence k(n) for every c >0 separately, whatever is the sequence xn satisfying the assumption
(*) . . . . 0 < xn ↗ ∞ such that xn+1 - xn → 0 as n → ∞ .
My suggestion is to use the following structure:
THEOREM. Under (*), for every c ≥ 0, there exists a sequence k(n) such that
(**) . . . . . xk(n) - xn → c .
Proof: The claim holds for c=0 trivially. For c>0 one can start with
LEMMA. The claim holds for c=1.
(I am omitting the proof of the Lemma since it's claim is contained in the fact formulated by George).
Now, for any other c>0, let us introduce yn := xn/c. This sequence satisfies the assumption of the theorem too. By the lemma for some sequence k(n) we have
(***) . . . . yk(n) - yn → 1
Multiplying statement (***) by c we arrive at (**).
Hopefully, it is correct, isn't it?
Best, Joachim
Addendum. Unfortunately, since I have missed some detail of George's problem, where he he stated the validity of the theorem just for 0
I was thinking of defining k(n) := sup { k ≥ n : xk - xn < c }. Then
xk(n) - xn < c ≤ xk(n)+1 - xn ,
and the length of the interval containing c is xk(n)+1 - xk(n) , which → 0 as n → ∞ by hypothesis.
Is this OK for all c > 0, or I am missing something?
It's ok, since both k's are well defined due to the divergence of xn .
JoaD
Dear George Stoica
I think you meant
the length of the interval is xk(n)+1 - xk(n) → 0 as n → ∞ .
Can you show the existence of the SUP as n → ∞?
Dear Joachim Domsta
The sequence xn is not necessarily a convergent sequence!
I think the sequence yn = m xn ( m > 0) satisfies all the requirements.
Proof:
yn+1 - yn = m (xn+1 - xn ) → 0
Obviously, yk(n) is a subsequence of yn , we have
yk(n) - yn = m (xk(n) - xn ) → mc as n → ∞.
So we select mc > 1.
Best regards
Dear Issam Kaddoura
JoaD: "both k's are well defined due to the divergence of xn . "
Thus, where did you see, that I was using convergence of xn , please?
With respect to your proof it does not differ from mine, but the fact that in your proof you depend on the clam for come c>0 and mine uses just c=1.
No substantial difference.
Best regards, Joachim
Dear Joachim,
I agree, yes, of course, it is your proof.
I repeat your proof without any additional assumptions.
Also, I think there was a misreading of some statements by my side. :)
Best regards
Thank you all for very good contributions; and also thank you for noticing the typo in my answer, I just corrected it.
P.S. I still have a small issue with my own solution, namely: is k(n) well defined, i.e., is k(n) always finite, or it depends upon c smaller/larger than 1? Please take a look...
I think k(n) is well defined.
To prove this, it suffices to realize that
If my arguments are correct, then k(n) is a maximum of the mentionned set, and the original statement holds for arbitrary c>0.
As usual, Viera provided a very convincing & compelling argument, that settles my doubt. Thank you!
To recap, up to now we have two good solutions. Thank you to all current contributors, you have done an excellent job!
You need a little more. To get a subsequence you must have k(n) strictly increasing. That does not follow from the construction. You need to find some way to make sure you have k(n) < k (n + 1).
Dear Viera Čerňanová
The set is not empty, but do you think that it is bounded?
In other words, does the supremum exist?
It seems to me that k(n) is unbounded.
Best Regards
It is bounded above, and in fact finite, because for a fixed n, x_k - x_n has limit infinity (as k goes to infinity) and after a finite number of values will be > c. So max can be used.
True, I was too optimistic by asking k(n) to be a subsequence; on the other hand, I can live (and so does the problem) with
"... then there exists k(n) → ∞ such that..."
instead of asking k(n) to be a subsequence etc.
Note that k(n) → ∞ because, by construction, k(n) ≥ n.
P.S. I think that the same remark applies to Joachim's solution as well.
Dear Issam Kaddoura , the proof that the set is finite lies in my second argument.
Dear Gabriel T. Prajitura you´re right.
Dear George Stoica , we can call the sequence {xk(n)} a stuttering subsequence * of {xn}. This would give birth to a new notion (unless it already exists). :)
* it is sure that {xk(n)} is non-decreasing because {xn} is increasing
Hi everybody,
The set { k ≥ n : x_k - x_n < c } may be empty up to some order n_0. Therefore we have to start from a given n_0 so that $x_{k+1} - x_k < c$ given by the convergence.
I think that we can make the $x_{k(n)}$ a real subsequence, as follows:
Choose $k_0$ so that $x_{k_0 + 1} - x_{k_0} < c$. Then take $k_1 = \sup{ k ≥ k_0 : x_k - x_{k_0} < c }$. Now by induction take $k_{n+1} = \sup{ k ≥ k_n : x_k - x_{k_n} < c }$. The sequence $(k_n)$ is increasing, since $k_{n+1}$ is at least $k_n + 1$. Now continu at noticed Stoica.
WARNING: For c>0 it is not true that
>> The set { k ≥ n : x_k - x_n < c } may be empty up to some order n_0.
You are right prof. Domsta. I wanted the subsequence to be increasing. This is why I did not care of k=n.
Thank you
Dear All,
just for having all our remarks in one, in the formulation I would replace the problem by a request of a proof of the following
THEOREM: Let 0 < xn ↗ ∞ be such that
(*) . . . . . . . xn+1 - xn → 0 as n → ∞ .
Then, for every c> 0 there exists a sequence k(n) such that xk(n) - xn → c as n → ∞ . The sequence can be chosen as nondecreasing.
PROOF (by construction): Let us fix c>0. By the assumed monotonicity and unboundedness of sequence xn , for every n there exists k ≥ n such that xk > xn + c. Such k is greater than n. Thus let us define k(n) ≔ min{ k≥n : xk > xn + c } [ which is greater than n and is equal to max{ k ≥ n : xk ≤ xn + c } +1 ]
Obviously, k(n) is nondecreasing. Moreover we have:
limn →∞ ( xk(n) - xn ) = c.
Indeed, otherwise there would exist an increasing sequence n(ℓ)→∞ , as ℓ→∞ , and such that for some positive ε >0
(**) . . . . . . . xk(n(ℓ)) - xn(ℓ) ≥ c + ε for ALL ℓ
On the other hand, by the definition of k(n), for every n we have xk(n)-1 - xn ≤ c for ALL n , in particular
(***) . . . . . . . xk(n(ℓ))-1 - xn(ℓ) ≤ c for ALL ℓ
Subtracting the inequalities (**) and (***) side by side, we arrive at
xk(n(ℓ)) - xk(n(ℓ))-1 ≥ ε for ALL ℓ
which contradicts the assumption (*).
Thank you, dear George, for the recommendation, but it is due to all P.T. Contributors of your intersting question.
I have just collected and exploited the main issues, remarks, suggestions, subquestions etc. Even those seemingly/allegedly wrong statements help those who care in reaching the rightest true:-)
All the best, Joachim
Dear Viera,
There is already a name for it: subnet. Sequences are nets and as such have subnets. some of which may not be subsequences. When they are not it is exactly because of repeating terms. But your name of the notion is more revealing!
Dear Joachim,
k(n) = n implies k(m) = m for all m < n, if you want to keep a subsequence.
We can define k(n) = n as long as x_(n+1) - x_n > c, which will be only for a finite number of values n, and use the max definition after that.
Dear George,
I am not sure it cannot be done with a subsequence. With a more complicated definition it may still be possible.
Gabriel - I am afraid, too, that's all we can get. I tried my "usual tricks", but nothing good came out. I'll leave this issue open, just in case.
Here is a statement with a subsequence :
THEOREM: Let $ 0 < x_n ↗ ∞$ be such that $x_{n+1} - x_n → 0$ as $n → ∞$ .
Then, for every c > 0 there exists a subsequence -$(x_{k(n)})_n$ of $(x_n)_n$ such that $x_{k(n+1)} - x_{k_n} → c$ as $n → ∞$.
PROOF: Fix $c > 0$. Since $x_{n+1} - x_n → 0$, there exists $n_0$ such that
$x_{n+1} - x_n < c$ for every $n ≥ n_0$.
Put $k(0) = n_0$ and assume constructed $k(0) < k(1) < ... < k(n)$ so that
$x_{k(j+1)} - x_{k(j)} < c$ and $c ≤ x_{k(j+1) + 1} - x_{k(j)}$, for every $j = 0, 1, n-1$. Now consider $k(n+1) = max{ k ≥ k(n) : $x_k - x_{k(n)} < c }$. Of course $k(n) < k(n+1)$, since $x_{k(n) + 1 } - x_{k(n)} < c$. Moreover, $c ≤ x_{k(n+1) + 1} - x_{k(n)}$ by the maximality. Now, since $(x_{k(n+1) + 1} - x_{k(n)}) - (x_{k(n+1)} - x_{k(n)}) = x_{k(n+1) + 1} - x_{k(n+ 1)}$ tends to 0, both sequences $x_{k(n+1)} - x_{k(n)}$ and $x_{k(n+1) + 1} - x_{k(n)}$ converge to $c$.
Notice that the sequence $x_{k(n+1) + 1} - x_{k(n)}$ also converges to $c$.
It is easier to read it in the attached file.
Dear Gabriel, you are suggesting that I "want to keep a subsequence". Sorry, do not.
And if I wanted, then this should be a subsequence of what, please?
Next you write: " We can define k(n) = n as long as x_(n+1) - x_n > c, "
BUT for what the reason we should define k(n) = n?
Best, Jachim
It is correct, dear Lahbib, thank you! - can we adapt it (somehow) to obtain xk(n) - xn → c as n → ∞ ?
Dear Joachim,
If x_(n + 1) - x_n > c then the only possible value for k(n) is n. You said that above.
If we want x_k(n) to be a subsequence of x_n, once we have k(n) = n for some n then k(m) = m for all m
The assertion is true for the famous harmonic series Hn for all real values c ≥ 0. Namely,
Hn: = 1+1/2+1/3+ + +1/n (n = 1,2,…).
It is well known that
Hn ≈ ln n + γ + 1/(2n) as n → ∞ (1),
where γ ≈ 0.577215… is the Euler–Mascheroni constant. For any nonnegative real numbers a, put k(n) = n + [an], where [x] denotes the greatest integer not exceeding x. Then from (1) we find that
Hk(n) - Hn = Hn+[an] - Hn ≈ ln(n + [an]) - ln n - [an]/(2n(n + [an])) = ln(1+ [an]/n) - [an]/(2n(n + [an])) as n → ∞,
and hence since an ≤ [an] < an +1, we have
Hk(n) - Hn → ln(1+a) as n → ∞.
Finally, taking a = ec -1 with c ≥ 0 in the above limit relation, we obtain
Hk(n) - Hn → c as n → ∞, as asserted.
Dear Gabriel
>> If x_(n + 1) - x_n > c then the only possible value for k(n) is n. You said that above. If we want x_k(n) to be a subsequence of x_n, once we have k(n) = n for some n then k(m) = m for all m
Let a be a fixed real number such that ) 0 < a < 1, and let xn ≈ na, i.e., lim_(n → ∞) (xn/na) = 1. Let c ≥ 0 be any nonnegative real number. Put k(n) = n + [cn1-a/a] (n = 1,2,… ), where [x] denotes the greatest integer not exceeding x. Then it can be proved that
xk(n) - xn → c as n → ∞.
For example, if xn ≈ √n, then k(n) = n + [2c√n], then it is easy to show that
xk(n) - xn = (n + [2c√n])1/2 - n1/2 → c for all c ≥ 0.
Hence, the proposed assertion is true for all sequencec (xn) with xn ≈ na (0 < a < 1) with respect to all real values c ≥ 0.
Numeruos computations in Wolfram’s Mathematica 9 sugges the following extensions of results attributed in my previous two answers, given as follows.
Let a and b be fixed real numbers such that 0 < a ≤ 1, and let xn ≈ na/lnb n, i.e., lim_(n → ∞) (xn lnb n/na) = 1. Let c ≥ 0 be any nonnegative real number. Put
k(n) = n + [cn1-aln n/a] (n = 1,2,… ), (1)
where [x] denotes the greatest integer not exceeding x. Then
xK(n) - xn → c as n → ∞.
Remark 1. Notice that the values of the sequence k(n) given by (1) does not depend on b.
Remark 2. The case when a = 0, b = -1, i.e., the sequence xn ≈ ln n is not included here, but this case is in fact solved in my first answer concerning the harmonic series Hn:= 1 +1/2 + 1/3 + +1/n ≈ ln n with related required subsequence k(n) = n + [(ec -1)n] (c ≥ 0).
Remark 3. The cases when a = 0 and (then must be) b < 0 also are not included here, i.e., the cases of the logarithmic sequences of the form xn ≈ ln-b n with any real value b < 0. A computation in Mathematica 9 (which also can be proved using L’Hospital rule) shows that for the sequence xn ≈ ln2 n, the corresponding required subsequence is k(n) = n + [nc/(2ln n)] (c ≥ 0).
A particular case (with a = b =1) of sequences in my previous answer is the most famous sequence in Number Theory (and one of the most famous sequence in Mathematics) xn = π (n) ≈ n/ln n with the related required subsequence k(n) = n + [cln n] (n = 1,2,…; c ≥ 0). Namely, the Prime Number Theorem describes the asymptotic distribution of the prime numbers among the positive integers. More precisely, the Prime Number Theorem gives an asymptotic form for the prime counting function π (n), which counts the number of prime numbers less than some integer n, as follows:
π (n) ≈ n/ln n as n → ∞.
(see, e.g., https://en.wikipedia.org/wiki/Prime_number_theorem#:~:text=In%20number%20theory%2C%20the%20prime,numbers%20among%20the%20positive%20integers.&text=This%20means%20that%20for%20large,1%20%2F%20log(N).
Hence, for each nonnegative real number c,
π(n + [cln n]) - π (n) → c as n → ∞.
Dear Romeo,
I like your proposition, however with a feeling that it is just a conjecture. My doubts came from the reading of the Prime Numbers Theorem on their distribution which state only that the RATIO of pi (n)/ [ n / ln n ] possesses a positive limit.
Probably this is NOT sufficient for inferring your proposition from the true theorem about the sequence n /ln n.
Continued:
Consider, please as a candidate for a counterexample the sequence
cn:= ( n + 2^([ log_2 (log_2(n)) ] ) / log_2 (n) for n > 1,
where again [ k ] stands for the integer part of k. Seemingly, it satisfies the following
cn / ( n log_2 (n) ) -> 1
c (n+1) - cn DOES NOT approach 0.
It holds for every positive (if tends to plus infinity) and negative (if tends to minus infinity) value of constant c.
Dear Yoachim Domsta,
You are right. It is well known in Number Theory that for the prime counting function π (n), π (n) ≈ n/ln n as n → ∞ (the asymptotic law of distribution of prime numbers), and π (n) - n/ln n > n/ln^2 n for all n ≥ 599. (see, e.g., https://en.wikipedia.org/wiki/Prime_number_theorem). Hence, π (n) - n/ln n → ∞ as n → ∞ (this is in fact, Sloane's OEIS sequence A057835, https://oeis.org/A057835).
However, motivated by the fact that for each fixed c ≥ 0, the subsequence xk(n) with k(n) = n + [cln n] of the sequence xn: = n/ln n (n = 1, 2, ...) satisfies the limit relation
xk(n) - xn → c as n → ∞,
it would be of interest to investigate the values of integer sequences
dn(c): = π(n + [cln n]) - π (n) (n = 1, 2, ...) for any fixed c ≥ 0.
Related investigations are well known as very hard problems in Analytic Number Theory concerning the asymptotic estimates of number of prime numbers in a short interval (especially, in our case in an interval I(n, c): = (n, n + [cln n]] which exactly contains π(n + [cln n]) - π (n) prime numbers).
My computations in Mathematica 9 show that for some fixed values c > 0, the values π(n + [cln n]) - π (n) are very close to c (and sometimes equal to c) for sufficiently large values n = n(c). This suggests the formulation of some “discrete version” of this problem proposed by George Stoica, concerning some classes of nondecreasing positive integer sequences that tend to infinity.
Dear Romero,
Set me straight if I am wrong:
Fulfiling the estimate π (n) - n/ln n > n/ln^2 n for all n ≥ 599 jointly with the PNT also are not sufficient for deriving the following claim made by you:
>> for each nonnegative real number c,
π(n + [cln n]) - π (n) → c as n → ∞.