Hunter Liu's Website

Use a proof by contraposition! Keep the assumptions of the statement, but negate the conclusion. Suppose that $\left\lbrace a_n \right\rbrace$ is as in the problem statement, but suppose that there exists some $\epsilon > 0$ such that for every $n$, there exist $n_1, n_2\geq n$ such that $\left\lvert a _{n_1} - a _{n_2} \right\rvert \geq \epsilon$.

The main idea of a proof by contraposition is: if you are trying to prove the statement “$P$ implies $Q$”, it’s the same thing as proving “not $Q$ implies not $P$”. (This is the contrapositive of the original statement.)

A good trick for negating statements is that you should turn every “for all” into a “there exists” and replace every “there exists” with a “for all” in the conclusion. Of course, you also need to flip all the inequalities.

Note: I originally called this a proof by contradiction, but it’s really not that — here, we show “not (Q) implies not (P)”, whereas a proof by contradiction is “show that (P) and not (Q) is never true”. They are very slightly different, and I’m sorry for the mistake!

Suppose that there exists some $\epsilon > 0$ such that for every $n$, there exist $n_1, n_2\geq n$ such that $\left\lvert a _{n_1} - a _{n_2} \right\rvert \geq \epsilon$. Fix such an $\epsilon$.

Let $m_1=1$. By assumption, there exists some $n_1,n_2\geq m_1$ such that $\left\lvert a _{n_1}-a _{n_2} \right\rvert \geq \epsilon$; let $m_2=\max \left( n_1,n_2 \right)$. Then $a _{m_2}- a _{m_1} \geq \epsilon$. (Why?)

Inductively continue this sequence: given some $m_i$, one may define a $m _{i+1}$ by repeating the above process. By assumption, there exist some $n_1,n_2\geq m_i$ such that $\left\lvert a _{n_1}- a _{n_2} \right\rvert> \epsilon$. After selecting $m _{i+1}=\max \left( n_1, n_2 \right)$, we get $a _{m_{i+1}} - a _{m_i} \geq \epsilon$.

We have now found a subsequence $\left\lbrace a _{m_i} \right\rbrace$ such that each term increases by at least $\epsilon$. But this means that the sequence $\left\lbrace a_n \right\rbrace$ is unbounded! This proves the contrapositive of the problem. $\square$

Fix any $\epsilon>0$. Let $j$ be the largest integer such that $M-j\epsilon$ is still an upper bound for the sequence $\left\lbrace a_n \right\rbrace$. Such a $j$ does exist: $j$ is at least $0$ since $M$ is already an upper bound, and $j$ cannot be larger than $\frac{M-a_n}{\epsilon}$ for any $n$. (We are, at some level, applying the well-ordering principle here.)

Let $M’=M-j\epsilon$, which is an upper bound of $\left\lbrace a_n \right\rbrace$. By construction, $M’-\epsilon=M-(j+1)\epsilon$ cannot be an upper bound of $\left\lbrace a_n \right\rbrace$, so there exists some $n_\epsilon$ such that $a _{n_\epsilon}\geq M’-\epsilon$. But then $a_n$ is between $M’-\epsilon$ and $M’$ for all $n\geq n_\epsilon$! It follows that for any $n_1\geq n_2\geq n_\epsilon$, $$\left\lvert a _{n_1}-a _{n_2} \right\rvert=a _{n_1}-a _{n_2}\leq M’-\left( M’-\epsilon \right)=\epsilon.$$ $\square$

Some people tried using a direct proof that used a least upper bound of the sequence. This is good because if $M_0$ is the least upper bound, then for every $\epsilon>0$, there exists an $n_\epsilon$ such that $a _{n_\epsilon}>M_0-\epsilon$; this is what makes our argument work. However, we have not constructed the real numbers yet, and we cannot use least upper bounds!

At the end of the day, the two proofs have very similar flavours. The first proof argues that if the conclusion is false, then the sequence will “step up” by $\epsilon$ infinitely many times, contradicting boundedness. The second proof argues that if the sequence is bounded, one can lower the bound to “within an $\epsilon$” of the sequence, which allows us to control how spread out the sequence is.

By definition, $\left\lbrace a_n+c_n \right\rbrace\sim \left\lbrace b_n+d_n \right\rbrace$ if $\lim _{n\to\infty} \left\lvert \left( a_n+c_n \right)-\left( b_n+d_n \right) \right\rvert=0$. By definition, this means that for each $\epsilon>0$ there exists some $n _{\epsilon}$ such that for all $n > n _{\epsilon}$, $$\left\lvert \left( a_n+c_n \right)-\left( b_n+d_n \right) \right\rvert< \epsilon.$$ By the triangle inequality (see the hint above), we have that $$\left\lvert \left( a_n+c_n \right)- \left( b_n+d_n \right) \right\rvert = \left\lvert \left( a_n-b_n \right) + \left( c_n-d_n \right) \right\rvert \leq \left\lvert a_n-b_n \right\rvert+ \left\lvert c_n-d_n \right\rvert.$$ The idea is that both quantities at the very right should “eventually be very small”, and this forces the quantity at the left to be “eventually be very small” as well. This is what we want!

Fix an $\epsilon>0$. Since $\left\lbrace a_n \right\rbrace\sim \left\lbrace b_n \right\rbrace$, $\lim _{n\to\infty} \left\lvert a_n-b_n \right\rvert=0$. Thus, there exists some $N_1$ such that whenever $n\geq N_1$, $\left\lvert a_n-b_n \right\rvert < \frac{\epsilon}{2}$. Similarly, since $\left\lbrace c_n \right\rbrace\sim \left\lbrace d_n \right\rbrace$, $\lim _{n\to\infty}\left\lvert c_n-d_n \right\rvert=0$, so there exists some $N_2$ so that whenever $n\geq N_2$, $\left\lvert c_n-d_n \right\rvert< \frac{\epsilon}{2}$.

Let $n _{\epsilon}=\max\left( N_1,N_2 \right)$. If $n \geq n _{\epsilon}$, then $n\geq N_1$, so $\left\lvert a_n-b_n \right\rvert < \frac{\epsilon}{2}$. Similarly, if $n\geq n _{\epsilon}$, then $n\geq N_2$, so $\left\lvert c_n-d_n \right\rvert< \frac{\epsilon}{2}$ as well. Using the triangle inequality from before, we get that for all $n \geq n _{\epsilon}$ that $$\left\lvert \left( a_n+c_n \right)-\left( b_n+d_n \right) \right\rvert <= \left\lvert a_n-b_n \right\rvert+\left\lvert c_n-d_n \right\rvert< \frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon.$$ This works for any $\epsilon>0$, so we conclude that $\lim _{n\to\infty}\left\lvert \left( a_n+c_n \right)-\left( b_n+d_n \right) \right\rvert=0$. Thus, $\left\lbrace a_n+b_n \right\rbrace\sim \left\lbrace c_n+d_n \right\rbrace$ by definition. $\square$

Let’s consider two cases:

1. $A$ knows at least $3$ other people.
2. $A$ knows fewer than $3$ other people. Necessarily, this means that $A$ doesn’t know at least $3$ other people.

Case 1: Suppose $A$ knows at least $3$ other people. Without loss of generality, we may assume that $A$ knows $B$, $C$, and $D$. If $B$, $C$, and $D$ all don’t know each other, then we’ve found three people that don’t know each other. Otherwise, at least two of them know each other, say $B$ and $C$, hence $A, B$, and $C$ all know each other!

The second case is more or less the same argument.

Case 2: Suppose $A$ doesn’t know at least $3$ other people. Again, we may assume that $A$ doesn’t recognise $B$, $C$, and $D$. If these three strangers to $A$ all know each other, we’re done! Otherwise, at least two of them don’t know each other, say $B$ and $C$; thus $A$, $B$, and $C$ are all strangers to each other. $\square$

Following the hint, we’ll consider two cases:

1. The sequence $\left\lbrace a_n \right\rbrace$ has infinitely many scenic viewpoints.
2. The sequence $\left\lbrace a_n \right\rbrace$ has finitely many scenic viewpoints.

Case 1: Let $n_1$ be the first scenic viewpoint, $n_2$ be the second scenic viewpoint, etc. Then $\left\lbrace a _{n_j} \right\rbrace$ is a monotone nonincreasing subsequence — each scenic viewpoint “overlooks” the rest of them!

Case 2: Let $N$ be the last scenic viewpoint in the sequence. Let $n_1>N$. $n_1$ can’t be a scenic viewpoint since it’s beyond the last scenic viewpoint in the sequence. Thus, there exists some $n_2>n_1$ with $a _{n_2} > a _{n_1}$. But $n_2$ is also past the last scenic viewpoint, so it isn’t a scenic viewpoint!

We can repeat this construction inductively to produce a monotone increasing subsequence. Given the $j$-th term $n_j$ of the subsequence, we know that it must be past the last scenic viewpoint and hence isn’t a scenic viewpoint itself. Thus, there exists some $n _{j+1}> n_j$ such that $a _{n _{j+1}} > a _{n_j}$.

By construction, we see that $\left\lbrace a _{n_j} \right\rbrace$ is a monotone increasing subsequence, concluding the second case. $\square$