0
$\begingroup$

I am aware that there are other posts discussing the same proposition. However, I would like to get feedback on my particular solution, which I have not been able to find on the forum. Thank you :)


We can construct a monotone subsequence given any sequence.

We will try to construct two monotone subsequences simultaneously, one increasing and one decreasing. One will be completed, the other will not.

Consider any sequence $(x_n).$

Start the following process with $n = 1$ (the first element in the sequence).

PROCESS: Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n \leq x_{n'},$ or there does not.

  1. If there does not exist such an element after $x_n,$ then all elements $x_{n'}$ after $x_n$ satisfy $x_{n'} < x_n.$ Add $x_n$ as the next element in the monotone decreasing sequence. Wipe clean the monotone increasing sequence under construction, and look at $x_{n+1}$ and start over.

  2. If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over.

Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.

If there is no monotone increasing subsequence, every attempt at sequentially constructing a monotone increasing sequence will eventually fail, arriving at an peak element $x_p,$ after which there is no element greater or equal to it (that is, there is no element that appears after it in the sequence that satisfies the monotone increasing condition), and Condition 1 will be satisfied infinitely many times, therein sequentially constructing a monotone decreasing subsequence.

$\endgroup$
1
$\begingroup$

There's a flaw at this part of the argument:

Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.

Consider this sequence for $n\geq2$:

$$\frac{(-1)^n}{n}=\frac12,-\frac13,\frac14,-\frac15,\frac16,-\frac17,\frac18,-\frac19,\ldots$$

There is a monotonically increasing subsequence: $-\frac13,-\frac15,-\frac17,\ldots$. However, your algorithm fails to find it. Instead, it steps through each value of $n$, wiping clean the increasing sequence under construction at every other step.

I'm not sure whether or not this sort of counterexample completely dooms your "greedy" algorithm, but it's false as stated.

$\endgroup$
15
  • $\begingroup$ Hi, Chris. I don't see how it will fail to find that subsequence. Once $\frac{-1}{3}$ is found, it will find $\frac{-1}{5},$ and then $\frac{-1}{7}$ and so on. Notice that condition 2 does specify that the element greater than the current element must be the very next element. $\endgroup$ – Rafael Vergnaud Jan 28 '19 at 23:34
  • $\begingroup$ "Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n \leq x_{n'},$ or there does not." $\endgroup$ – Rafael Vergnaud Jan 28 '19 at 23:39
  • $\begingroup$ "If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over." $\endgroup$ – Rafael Vergnaud Jan 28 '19 at 23:39
  • $\begingroup$ Having arrived at $\frac{-1}{3},$ there will be a later element in the sequence that is greater or equal to $\frac{-1}{3}.$ It will add that element, and then start the process over by looking at that element. And so on $\endgroup$ – Rafael Vergnaud Jan 28 '19 at 23:40
  • $\begingroup$ @RafaelVergnaud It's not a well-defined process if you don't specify any way to know which $n'$ is going to be selected. You might as well write "Let $n'$ be the index that gives me the result I'm hoping for." $\endgroup$ – Chris Culter Jan 28 '19 at 23:42
1
$\begingroup$

This is indeed, in essence, the standard proof for this fact.

$\endgroup$
4
1
$\begingroup$

(1). If $\lim_{n\to \infty}a_n=a$ then $(a_n)_n$ has a monotone sub-sequence $(a_{f(n)})_n.$ Proof: Let $C=\{n:a_n=a\}.$ Let $P=\{n:a_n>a\}$ and $Q=\{n:a_n<a\}.$

$\quad$ (i). If $C$ is infinite let $f:\Bbb N\to C$ be the unique strictly increasing bijection.

$\quad$ (ii). If $C$ is finite and $P$ is infinite let $f(1)=\min P$ and let $f(n+1)=\min \{j>f(n): a< a_j< a_{f(n)}\}.$

$\quad$ (iii). If $S$ and $P$ are finite let $f(1)=\min Q$ and let $f(n+1)=\min \{j>f(n):a_{f(n)}<a_j<a\}.$

(2). A bounded sequence $(b_n)_n$ has a convergent sub-sequence $(b_{g(n)})_n.$ Proof: Suppose $\{b_n:n\in \Bbb N\}\subset [l,u].$

Let $[l_1,u_1]=[l,u]$ and let $g(1)=1.$

For convenience, for any $n$ let $m_n=(l_n+u_n)/2.$

Now if $\{n:b_n\in [l_n,m_n]\}$ is infinite let $[l_{n+1},u_{n+1}]=[l_n,m_n];$ otherwise let $[l_{n+1},u_{n+1}]=[m_n,u_n].$ And in either case let $g(n+1)=\min \{j>g(n):b_j\in [l_{n+1},u_{n+1}]\}.$

Observe that $|b_{g(n)}-b_{g(n+1)}|\le u_n-l_n=2^{1-n}(u-l)$, which implies that $(b_{g(n)})_n$ is a Cauchy sequence.

(3). Let $b_n=\arctan x_n \in (-\pi/2,\pi/2).$ By (2) there exists a convergent sub-sequence $(b_{g(n)})_n$ and by (1), with $a_n=b_{g(n)},$ the sequence $(b_{g(n)})_n$ has a monotone sub-sequence $(b_{g(f(n))})_n.$ Since $\tan $ is a monotone function on the domain $(-\pi/2,\pi/2),$ therefore $$(\tan b_{g(f(n))})_n=(x_{g(f(n))})_n$$ is monotone.

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