Week 7 Discussion Notes

Solution.

Base case: ($n = 0$)

When $n = 0$, we get $2^0 = 1 = 1!$, so the base case holds.

Inductive step:

Suppose $2^n \leq \p{n+1}!$. We want to show that $2^{n+1} \leq \p{n+2}!$ also. First, notice that since $n \geq 0$, we get $n + 2 \geq 2$. Thus,

By induction, the inequality holds for all $n \geq 0$.

Solution.

1. We'll do this by induction.

   Base case: ($n = 0$)

   By definition, $s_0 = \frac{1}{2} \in \br{0, 1}$ already, so the base case holds.

   Inductive step:

   Suppose that $s_n \in \br{0, 1}$, or equivalently, that $0 \leq s_n \leq 1$. Then by cubing everything, we get

   $$0^3 \leq s_n^3 \leq 1^3 \implies 0 \leq s_{n+1} \leq 1,$$

   since $s_{n+1} = s_n^3$ by definition. Thus, by induction, $s_n \in \br{0, 1}$ for all $n \geq 0$.

2. First, notice that

   $$s_n - s_{n+1} = s_n - s_n^3 = s_n\p{1 - s_n^2}.$$

   By (1), we know that $s_n \geq 0$, and because $s_n \in \br{0, 1}$, we also know that $s_n^2 \leq 1$. Thus, $1 - s_n^2 \geq 0$, so $s_n - s_{n+1} \geq 0$ also, i.e., $s_n \geq s_{n+1}$, so $s_n$ is decreasing.

3. By (1) and (2), we see that $s_n$ is a bounded monotone sequence, so it converges to some $s$. Thus, by the limit laws, we can take limits on both sides of the recursive relation:

   $$s_{n+1} = s_n^3 \implies s = s^3 \implies s\p{1 - s^2} = 0.$$

   So, there are three possibilities: $s \in \set{-1, 0, 1}$. Since $s_n \geq 0$ for all $n \geq 0$, we get $s \geq 0$, so $s \neq -1$. Because $s_n$ is decreasing, we also know that $s_n \leq s_0 = \frac{1}{2}$, so $s \leq \frac{1}{2}$ also. Thus, $s = 0$.

Solution.

1. Let $M > 0$. Since $\displaystyle\lim_{n\to\infty} s_n = \infty$, there exists $N_1 \in \R$ such that if $n > N_1$, then $s_n \geq M$. Thus, if $n > \max\,\set{N_0, N_1}$, we get

   $$M \leq s_n \leq t_n.$$

   Since $M$ was arbitrary, this proves that $\displaystyle\lim_{n\to\infty} t_n = \infty$ also.

2. In Week 4, I proved a fact about non-negative sequences: if $\set{a_n}_n$ is a sequence such that $a_n \geq 0$ for all $n \geq 0$ and that $\displaystyle\lim_{n\to\infty} a_n$ exists, then $\displaystyle\lim_{n\to\infty} a_n \geq 0$.

   If we set $a_n = t_n - s_n$, then $a_n \geq 0$ (technically only for $n > N_0$, but this doesn't make a big difference since we're working with limits), then because all the limits in question exist, the proposition and the limit laws tell us

   $$\lim_{n\to\infty} t_n - \lim_{n\to\infty} s_n = \lim_{n\to\infty} \p{t_n - s_n} \geq 0 \implies \lim_{n\to\infty} s_n \leq \lim_{n\to\infty} t_n.$$

   Alternatively, if we didn't have this theorem, we can also prove it using the $\epsilon$ definition directly. Let $s = \displaystyle\lim_{n\to\infty} s_n$ and $t = \displaystyle\lim_{n\to\infty} t_n$, and suppose for the sake of contradiction that $s > t$.

   The idea is this: eventually, $s_n$ should be very close to $s$, and $t_n$ should be very close to $t$. If they're close enough, then we should eventually end up with $s_n > t_n$, which contradicts our assumption that $s_n \leq t_n$ for $n > N_0$.

   Let $\epsilon = \frac{s - t}{2}$, i.e., half the distance between $s$ and $t$. Since $s = \displaystyle\lim_{n\to\infty} s_n$, there exists $N_1 \in \R$ such that if $n > N_1$, then

   $$\begin{aligned} \abs{s_n - s} < \epsilon &\implies s_n - s > - \epsilon \\ &\implies s_n > s - \epsilon = s - \p{\frac{s - t}{2}} = \frac{s + t}{2}. \end{aligned}$$

   Similarly, there exists $N_2 \in \R$ such that if $n > N_2$, then

   $$\begin{aligned} \abs{t_n - t} < \epsilon &\implies t_n - t < \epsilon \\ &\implies t_n < t + \epsilon = t + \frac{t - s}{2} = \frac{s + t}{2}. \end{aligned}$$

   Thus, if $n > \max\,\set{N_0, N_1, N_2}$, then

   $$t_n \underbrace{<}_{n > N_2} \frac{s + t}{2} \underbrace{<}_{n > N_1} s_n \underbrace{\leq}_{n > N_0} t_n$$

   which is a contradiction.