Timeline for Chains or Antichains slowly increasing

6 events

when toggle format	what		by	license	comment
Apr 23, 2013 at 20:39	comment	added	Douglas Zare		There are monotone subsequences of this sequence with $a_n = O(n^2)$. $1/8, 3/8, 17/32, 19/32, 21/32, 23/32, 97/128, 99/128, ..., 111/128, 449/512, ...$. That is monotone. $a_1=4, a_2=5, a_3=24, a_4=25, a_5=26, a_6=27, a_7=112, a_8=113,... a_{14}=119, a_{15}=480...$. In this monotone subsequence, $a_{2^n-1} \lt 2^{2n+1}, a_n \le 4n^2$.
Apr 23, 2013 at 9:13	comment	added	Douglas Zare		Why is it a contradiction if $a_{n+1}-a_n \gt a_n/4$ infinitely often? If $a_n$ reads the decimal expansion of $n$ as a base $100$ number, then $a_{n+1} \gt 10 a_n$ infinitely often, whenever $n+1$ is a power of $10$, but $a_n \le n^2$. This construction may work, but it needs another argument.
Apr 23, 2013 at 0:52	comment	added	ilcapu		(Clearly the condition $a_n=O(n^2)$ would immediately imply the divergence of the series of reciprocals of gaps, but it`s effectively too strong.)
Apr 23, 2013 at 0:47	comment	added	ilcapu		Thank you Gerhard, your counterexample works. Actually i`m interested in a slighty different problem, i.e. if exists an infinite subset $A$ such that $\sigma_{\|A}$ is monotone and $$ \sum_{n=1}^{+\infty}\frac{1}{a_{n+1}-a_n}=+\infty$$ Your example don`t contradict this weakened version of the problem. Do you have some suggestion about this?
Apr 23, 2013 at 0:44	vote	accept	ilcapu
Apr 22, 2013 at 23:07	history	answered	Gerhard Paseman	CC BY-SA 3.0