Week 6 Discussion Notes

Solution.

You may be tempted to do the following: (which is wrong!)

If we take limits on both sides, then we get the equation $s = s^2$, so $s = 0$ or $s = 1$. Since $s_n < 1$ for $n \geq 1$, this means $s \neq 1$, so $s = 0$.

The problem is the very first step: this fake proof is trying to apply the limit laws without knowing if the limits exist or not. This is why it's important to do (1) before doing (2).

1. Generally, when you're given a recursive sequence like this, you want to prove that it's bounded and monotone (usual by induction, though it's not always necessary). We want to figure out whether the sequence is increasing or decreasing, so a good way to start is to write out a few terms and take a guess:

   $$s_1 = 1,\ s_2 = \frac{2}{3},\ s_3 = \frac{1}{3}.$$

   Based on this, we're going to guess that $s_n$ is decreasing. Since anything square is non-negative, we automatically get the lower bound $s_n \geq 0$. Next, we need to try to prove that the sequence is decreasing, i.e., we want to show that $s_{n+1} \leq s_n$. Generally, however, it's usually much easier to show that $s_{n+1} - s_n \leq 0$, so let's see what happens:

   $$\begin{aligned} s_{n+1} - s_n &= \frac{n}{n + 1} s_n^2 - s_n \\ &\leq \frac{n + 1}{n + 1} s_n^2 - s_n \\ &= s_n\p{s_n - 1}. \end{aligned}$$

   If we can show that $s_n - 1 \leq 0$, then we will have shown that the sequence decreases, so let's try to do that by induction:

   Base case: ($n = 1$)

   $s_1 = 1 \leq 1$, so the base case holds.

   Inductive step:

   Assume that $s_n \leq 1$. We need to show that $s_{n+1} \leq 1$ also:

   $$s_{n+1} = \frac{n}{n + 1} s_n^2 \leq \frac{n + 1}{n + 1} \cdot 1^2 = 1.$$

   Thus, the inductive step holds, so $s_n \leq 1$ for all $n \geq 1$. This also proves that $s_{n+1} \leq s_n$ for all $n \geq 1$, which means that $\set{s_n}_n$ is a decreasing sequence bounded below, so it converges.

2. Now that we know that the sequence converges, now we can take limits on both sides. Let $s = \lim_{n\to\infty} s_n$, so by our limit laws,

   $$\begin{gathered} \lim_{n\to\infty} s_{n+1} = \lim_{n\to\infty} \frac{n}{n + 1} s_n^2 = \p{\lim_{n\to\infty} \frac{n}{n + 1}} \p{\lim_{n\to\infty} s_n^2} \\ \implies s = 1 \cdot s^2 = s^2. \end{gathered}$$

   Thus, $s\p{s - 1} = 0$, which means $s = 0$ or $s = 1$. We saw that $s_n$ is decreasing, so $s_n \leq s_2 = \frac{2}{3}$ for all $n \geq 2$. This means that $s < 1$, so $s = 0$.

Solution.

The main idea is to use density of rationals over and over again, but in a careful way to get the properties we want. There are two things we want from our sequence:

1. It gets closer and closer to $a$. For concreteness, we want $a \leq q_n \leq a + \frac{1}{n}$ for each $n \geq 1$, but you can replace $\frac{1}{n}$ with any other positive sequence that converges to $0$ (another good choice is $\frac{1}{2^n}$).
2. It is a decreasing sequence.

To construct a sequence, we generally want to do it by induction and making sure that at each step, we pick a rational number that does both of these.

Base case: ($n = 1$)

Since $\Q$ is dense in $\R$, there exists a rational $q_1 \in \p{a, a + 1}$. To illustrate the inductive step, I will also do the case $n = 2$ by hand:

To accomplish (1), we want $q_2 \in \p{a, a + \frac{1}{2}}$. However, we need to also guarantee that $q_2 \leq q_1$, so we also need to require that $q_2 \in \p{a, q_1}$. Let $\epsilon = \min\,\set{\frac{1}{2}, q_1 - a}$, so $\p{a, a + \epsilon}$ is a non-empty interval. Thus, because $\Q$ is dense, there exists a rational $q_2 \in \p{a, a + \epsilon}$, and this satisfies both (1) and (2).

Inductive step:

Now suppose we have chosen $q_1, \ldots, q_n$ such that $q_k \in \p{a, a + \frac{1}{k}}$ and $a \leq q_n \leq q_{n-1} \leq \cdots \leq q_1$. Let $\epsilon = \min\,\set{\frac{1}{n+1}, q_n - a}$, so $\p{a, a + \epsilon}$ is a non-empty interval. By density of $\Q$, there exists a rational $q_{n+1} \in \p{a, a + \epsilon}$, and by construction,

Thus, the inductive step holds. By induction, we obtain a decreasing sequence $\set{q_n}_n$ such that $q_n \in \p{a, a + \frac{1}{n}}$ for each $n \geq 1$, i.e., $a \leq q_n \leq a + \frac{1}{n}$. By the squeeze theorem, $\lim_{n\to\infty} q_n = a$, which completes the proof.