4
$\begingroup$

I am experiencing some conceptual difficulties in part (a) exercise 2.4.7 of Understanding Analysis by Stephen Abbott (2015), and would appreciate some clarity concerning proof by induction.

Context.

Exercise 2.4.7 (Limit superior). Let $(a_n)$ be a bounded sequennce.

(a) Prove that the sequence defined by $y_n = \sup \{a_k : k \geq n \}$ converges.

In order to prove this using tools developed in that section of the book, I opted for using the monotone convergence theorem, which requires showing that $(y_n)$ is bounded and decreasing. Where I'm experiencing doubt is in showing that $(y_n)$ is decreasing using induction.

Proof by induction that $(y_n)$ is decreasing.

Base case $y_1 \geq y_2$. Because $y_1 = \sup \{a_k : k \geq 1 \}$, it is also an upper bound for $\{a_k : k \geq 2 \}$. Because $y_2 = \sup \{a_k : k \geq 2 \}$ is the least upper bound for $\{a_k : k \geq 2 \}$, it follows that $y_1 \geq y_2$.

Inductive step. Assume $y_{k} \geq y_{k+1}$ for some $k \in \mathbb{N}$, and call this statement $S(k)$.

As I understand, I need to deduce the truth of $S(k+1)$ from the assumption that $S(k)$ is true. But this is where I am experiencing doubt. To me, it seems that I can show the truth of $S(k+1)$, that $y_{k+1} \geq y_{k+2}$, using the same argument as in the base case and without needing to assume that $S(k)$ at all. Which raises the following queries.

Queries.

1) In this specific case, would it constitute a flaw in my induction strategy if I showed that $y_{k+1} \geq y_{k+2}$ without explicitly making use of the assumption that $S(k)$ is true? In the sense that I assume the truth of $S(k)$ as a formality, but don't explicitly use it to deduce the truth of $S(k+1)$.

2) If there is no need to assume $S(k)$ is true to deduce the truth of $S(k+1)$, then surely induction is inappropriate in the sense that this hints at a more direct proof?

3) Or is the fact that a sequence of suprema $(y_n)$ is decreasing for a bounded sequence $(a_n)$ something so obvious from applying definitions that it shouldn't need proof at all?

4) The last possibility I have in mind is that my previous questions are a reflection of the fact that I do not know how to explicitly articulate how $y_{k} \geq y_{k+1}$ can be used to deduce $y_{k+1} \geq y_{k+2}$. If so, how do I explicitly articulate it? See related threads below.

Previous questions.

This questions here concerns exactly the same exercise for solution verification, and the OP writes:

Assume that $y_k \geq y_{k+1}$. Then, $y_{k+1}=\sup\{a_k : k + 1 \geq n\}= \max\{a_{k+1}, y_{k+2} \} ≥ y_{k+2}.$

Whilst this intuitively seems obvious, to me it feels unnatural. But perhaps that's because I am having difficulty reconciling my intuitions with why this must be true formally. I would appreciate some explanation on this.

$\endgroup$
3
  • 1
    $\begingroup$ It seems to me that in this case you don't really need to use induction since the argument you've used in the base case works just as well for any $y_j, y_k$ such that $y_j<y_k$ so I would say that your point (2) is true. $\endgroup$
    – lorenzo
    Jul 31, 2021 at 0:08
  • 1
    $\begingroup$ I think your point (3) is correct. We just have to prove the intuitive theorem that $$A \subseteq B \implies \sup(A) \leq \sup(B).$$ To prove this we just note that for any $a \in A$, $a \leq \sup(B)$, so $\sup(A) \leq \sup(B)$. $\endgroup$
    – Mason
    Jul 31, 2021 at 0:08
  • $\begingroup$ @Mason. Thank you for the clear explanation. If you had posted this is as an answer, I would have accepted. It succinctly summarises what I was grasping at but unable to articulate. As the other answer was posted as an answer I accepted it, but you are welcome to post the comment as an answer and I will upvote accordingly. $\endgroup$
    – microhaus
    Jul 31, 2021 at 2:52

1 Answer 1

1
$\begingroup$
  1. No, it is not a flaw. In fact, it shows you don't need to use induction. I think beginners are overzealous with induction for whatever reason, but you don't have to use induction to prove every statement about integers. $y_k \geq y_{k+1}$ can be proven directly, just like $n(n+1) = n^2 + n$ can be proven directly.
  2. Yes, your argument is the direct proof.
  3. It is obvious for someone who understands analysis. However, in a first course in a subject, you should be as detail oriented as possible. The further you get in mathematics, the more 'obvious' things will be, but at the beginning stages of your mathematical career, you should spell details out since you don't have fully developed intuition for what is true and what requires proof yet (most mathematicians would say this is obvious because they see the proof immediately, not because they don't want to prove it). For example, when one first learns algebra they typically need to write out a long series of steps to solve simple equations like $2x+5 = 12,$ but after awhile many people can solve linear equations with small coefficients in their heads.
  4. Again, just don't induct.
$\endgroup$
1
  • $\begingroup$ +1. Thank you for addressing my queries, especially the remark concerning beginners being overzealous with induction useful. I had googled whether induction was frowned upon as a matter of taste compared to direct proof; but in this case it looks like there are concrete substantive reasons to opt for the latter. $\endgroup$
    – microhaus
    Jul 31, 2021 at 2:58

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.