<Home>Teaching><MATH 131A (Winter 2021)>Week 5 Discussion Notes

Week 5 Discussion Notes

Table of Contents

Homework Comments

Now that the homework problems are a bit more interesting, I have relatively important comments to make.

1.9

This was the problem where you had to prove that 2n>n22^n > n^2 for all n≥5n \geq 5 by induction. I saw a lot of proofs that looked like this:

2n+1=2⋅2n>2n2>n2+2n+1(since n≥5)=(n+1)2.\begin{aligned} 2^{n+1} &= 2 \cdot 2^n \\ &> 2n^2 \\ &> n^2 + 2n + 1 && \p{\text{since } n \geq 5} \\ &= \p{n + 1}^2. \end{aligned}

I mainly had issue with the third line: while it is true that n2>2n+1n^2 > 2n + 1 when n≥5n \geq 5, you still have to prove it on your homework. As a general rule of thumb, you should prove all claims you make that weren't proven in lecture, discussion, or the book (unless Professor Jacobs or I say it's okay to take something for granted). That being said, here is one way to prove it: since n≥5≥3n \geq 5 \geq 3,

n2=n⋅n≥3n=2n+n>2n+1.n^2 = n \cdot n \geq 3n = 2n + n > 2n + 1.

Miscellaneous

Let P,QP, Q be propositional statements. If P  ⟹  QP \implies Q is true and QQ is true, does this mean PP is also true? Hopefully, you agree that this is a false statement, and we can check with a logic table:

PQP  ⟹  Q111100011001\begin{array}{ccc} P & Q & P \implies Q \\\hline 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{array}

The third row is the important row for this example: QQ is true and P  ⟹  QP \implies Q is true, but PP is false. With this in mind, consider the following example:

Example 1.

What's the problem with the following argument?

Note that

n2−2n−1≥0  ⟹  (n−1)2−2≥0  ⟹  (n−1)2≥2.\begin{aligned} n^2 - 2n - 1 \geq 0 &\implies \p{n - 1}^2 - 2 \geq 0 \\ &\implies \p{n - 1}^2 \geq 2. \end{aligned}

This is true if n≥3n \geq 3. Therefore, n2−2n−1≥0n^2 - 2n - 1 \geq 0 when n≥3n \geq 3.
Solution.

While the conclusion is true, the proof (which is the most important part) is incorrect: set P=‘‘n2−2n−1≥0"P = ``n^2 - 2n - 1 \geq 0" and Q=‘‘(n−1)2≥2"Q = ``\p{n - 1}^2 \geq 2", and we assume that n≥3n \geq 3. Then the incorrect proof is using the following logic:

P  ⟹  QP \implies Q is true and QQ is true. Therefore PP is true.

As we discussed, this logic is not correct. Instead, you should do this in reverse: show that something true implies something else is true. In this case, the proof is correct if we just reverse the order of the steps: for n≥3n \geq 3,

(n−1)2≥2  ⟹  n2−2n+1≥2  ⟹  n2−2n−1≥0,\begin{aligned} \p{n - 1}^2 \geq 2 &\implies n^2 - 2n + 1 \geq 2 \\ &\implies n^2 - 2n - 1 \geq 0, \end{aligned}

and now you can conclude that n2−2n−1≥0n^2 - 2n - 1 \geq 0 for n≥3n \geq 3.

Limits

Limit Laws

Theorem (limit laws)

Suppose lim⁡n→∞an=a\displaystyle\lim_{n\to\infty} a_n = a and lim⁡n→∞bn=b\displaystyle \lim_{n\to\infty} b_n = b. Then:

  1. lim⁡n→∞(an+bn)=a+b\displaystyle\lim_{n\to\infty} \p{a_n + b_n} = a + b.
  2. If c∈Rc \in \R, then lim⁡n→∞can=ca\displaystyle\lim_{n\to\infty} ca_n = ca.
  3. lim⁡n→∞(anbn)=ab\displaystyle\lim_{n\to\infty} \p{a_nb_n} = ab.
  4. If b≠0b \neq 0, then lim⁡n→∞anbn=ab\displaystyle\lim_{n\to\infty} \frac{a_n}{b_n} = \frac{a}{b}.

This looks like a straightforward theorem, but it can be very easy to misuse it. The most common way I've seen it be used incorrectly is trying to apply it with limits that don't exist.

Example 2.

If lim⁡n→∞an\displaystyle\lim_{n\to\infty} a_n and lim⁡n→∞bn\displaystyle\lim_{n\to\infty} b_n don't exist, does this mean an+bna_n + b_n doesn't exist?
Solution.

The following is wrong:

lim⁡n→∞(an+bn)=lim⁡n→∞an+lim⁡n→∞bn\displaystyle\lim_{n\to\infty} \p{a_n + b_n} = \displaystyle\lim_{n\to\infty} a_n + \displaystyle\lim_{n\to\infty} b_n, and these limits don't exist. Therefore, lim⁡n→∞(an+bn)\displaystyle\lim_{n\to\infty} \p{a_n + b_n} doesn't exist either.

The problem is with the first "=" sign: the limits don't exist, so that "=" is invalid. As a counterexample, consider an=(−1)na_n = \p{-1}^n and bn=−(−1)nb_n = -\p{-1}^n. Then both limits don't exist, but

lim⁡n→∞(an+bn)=lim⁡n→∞((−1)n−(−1)n)=lim⁡n→∞0=0,\lim_{n\to\infty} \p{a_n + b_n} = \lim_{n\to\infty} \p{\p{-1}^n - \p{-1}^n} = \lim_{n\to\infty} 0 = 0,

so it's possible that the sum of two divergent sequences is convergent.
Exercise 1.

Come up with an example where {an}n\set{a_n}_n and {bn}n\set{b_n}_n are divergent, but {anbn}n\set{a_nb_n}_n is divergent.

Limit laws are very useful because if we can use them, then we don't need to do any ε\epsilon arguments.

Example 3.
(Related to 9.1, 9.3)

Suppose lim⁡n→∞an=a\displaystyle\lim_{n\to\infty} a_n = a and lim⁡n→∞bn=b\displaystyle\lim_{n\to\infty} b_n = b. Calculate lim⁡n→∞2an2+1bn2+2\displaystyle \lim_{n\to\infty} \frac{2a_n^2 + 1}{b_n^2 + 2} and justify all your steps.
Solution.

This example is basically here to illustrate the amount of detail I expect on 9.1 and 9.3 (if you want full credit).

lim⁡n→∞an=a\displaystyle\lim_{n\to\infty} a_n = a, so lim⁡n→∞(2an2+1)=2a2+1\displaystyle\lim_{n\to\infty} \p{2a_n^2 + 1} = 2a^2 + 1 by (i), (ii), and (iii), and similarly, lim⁡n→∞(bn2+1)=b2+1\displaystyle\lim_{n\to\infty} \p{b_n^2 + 1} = b^2 + 1 by (i) and (iii). Since b2+1>0b^2 + 1 > 0, we can use (iv) to get

lim⁡n→∞2an2+1bn2+2=lim⁡n→∞(2an2+1)lim⁡n→∞(bn2+2)=2a2+1b2+2.\lim_{n\to\infty} \frac{2a_n^2 + 1}{b_n^2 + 2} = \frac{\lim_{n\to\infty} \p{2a_n^2 + 1}}{\lim_{n\to\infty} \p{b_n^2 + 2}} = \frac{2a^2 + 1}{b^2 + 2}.

Basically, every "=" needs to be justified (with a few words).

Another (very) useful theorem for calculating limits is the squeeze theorem:

Theorem (squeeze theorem)

Let {an}n\set{a_n}_n, {bn}n\set{b_n}_n, and {sn}n\set{s_n}_n be sequences such that an≤sn≤bna_n \leq s_n \leq b_n. If lim⁡n→∞an=lim⁡n→∞bn=L\displaystyle\lim_{n\to\infty} a_n = \lim_{n\to\infty} b_n = L, then lim⁡n→∞sn=L\displaystyle \lim_{n\to\infty} s_n = L also.
Proof.

Let ε>0\epsilon > 0. Notice that

sn−L≤bn−L≤∣bn−L∣and−∣an−L∣≤an−L≤sn−L.s_n - L \leq b_n - L \leq \abs{b_n - L} \quad\text{and}\quad -\abs{a_n - L} \leq a_n - L \leq s_n - L.

Since lim⁡n→∞an=L\displaystyle\lim_{n\to\infty} a_n = L, there exists N1∈RN_1 \in \R such that

n>N1  ⟹  ∣an−L∣<ε  ⟹  −ε<−∣an−L∣≤sn−L.\begin{aligned} n > N_1 &\implies \abs{a_n - L} < \epsilon \\ &\implies -\epsilon < -\abs{a_n - L} \leq s_n - L. \end{aligned}

Similarly, because lim⁡n→∞bn=L\displaystyle\lim_{n\to\infty} b_n = L, there exists N2∈RN_2 \in \R so that

n>N2  ⟹  ∣bn−L∣<ε  ⟹  sn−L≤∣bn−L∣<ε.\begin{aligned} n > N_2 &\implies \abs{b_n - L} < \epsilon \\ &\implies s_n - L \leq \abs{b_n - L} < \epsilon. \end{aligned}

These inequalities work for different conditions on nn, but we want to use them at the same time. If we let N=max⁡ {N1,N2}N = \max\,\set{N_1, N_2}, then whenever n>Nn > N, nn satisfies n>N1n > N_1 and n>N2n > N_2 at the same time. Thus,

−ε<sn−L<ε  ⟹  ∣sn−L∣<ε.-\epsilon < s_n - L < \epsilon \implies \abs{s_n - L} < \epsilon.

□\square

We generally use the following corollary of the squeeze theorem the most:

Corollary

Let {sn}n\set{s_n}_n and {tn}n\set{t_n}_n be sequences such that ∣sn∣≤tn\abs{s_n} \leq t_n and lim⁡n→∞tn=0\displaystyle\lim_{n\to\infty} t_n = 0. Then lim⁡n→∞sn=0\displaystyle\lim_{n\to\infty} s_n = 0.
Proof.

Observe that −tn≤sn≤tn-t_n \leq s_n \leq t_n. Thus, if we set an=−tna_n = -t_n and bn=tnb_n = t_n as in the theorem, then an≤sn≤bna_n \leq s_n \leq b_n and

lim⁡n→∞an=lim⁡n→∞bn=0  ⟹  lim⁡n→∞sn=0.\lim_{n\to\infty} a_n = \lim_{n\to\infty} b_n = 0 \implies \lim_{n\to\infty} s_n = 0.

□\square

This corollary helps speeds up proofs quite a bit:

Example 4.

Prove that lim⁡n→∞∣n+2n2+1∣=0\displaystyle \lim_{n\to\infty} \abs{\frac{n + 2}{n^2 + 1}} = 0.
Solution.

In light of the squeeze theorem, we just need to find something bigger than ∣n+2n2+1∣\abs{\frac{n + 2}{n^2 + 1}} which goes to 00:

∣n+2n2+1∣≤n+nn2≤2n→n→∞0.\abs{\frac{n + 2}{n^2 + 1}} \leq \frac{n + n}{n^2} \leq \frac{2}{n} \xrightarrow{n\to\infty} 0.

(The arrow can be read as "... which goes to 00 as n→∞n \to \infty".)

Proving Divergence

As a quick example (relevant for your homework), here are two problems where you need to show that a limit doesn't exist:

Example 5.

Let a2n=1a_{2n} = 1 and a2n+1=3a_{2n+1} = 3. Show that lim⁡n→∞an\displaystyle\lim_{n\to\infty} a_n does not exist.
Solution.

Suppose otherwise and that lim⁡n→∞an=L\displaystyle\lim_{n\to\infty} a_n = L. Then given ε>0\epsilon > 0, there exists N∈RN \in \R such that whenever ∣an−L∣<ε\abs{a_n - L} < \epsilon whenever n>Nn > N.

Suppose k>N2k > \frac{N}{2}. Then

2k>N  ⟹  ∣a2k−L∣<ε.2k > N \implies \abs{a_{2k} - L} < \epsilon.

Similarly,

2k+1>N  ⟹  ∣a2k+1−L∣<ε.2k + 1 > N \implies \abs{a_{2k+1} - L} < \epsilon.

Based on these inequalities, if nn is big enough, then LL is within ε\epsilon of 11 and 33. In the picture, this means that LL has to be in both blue parentheses, and this should be impossible if ε\epsilon is small enough. Based on the picture, we should get a contradiction if we let ε=1\epsilon = 1:

2=∣1−3∣=∣a2k−a2k+1∣≤∣a2k−L∣+∣a2k+1−L∣<1+1=2.2 = \abs{1 - 3} = \abs{a_{2k} - a_{2k+1}} \leq \abs{a_{2k} - L} + \abs{a_{2k+1} - L} < 1 + 1 = 2.

This is impossible, so no LL could have existed to begin with, which completes the proof.
Example 6.

Let an=2na_n = 2^n. Prove that lim⁡n→∞2n\displaystyle\lim_{n\to\infty} 2^n does not exist.
Solution.

Like before, we're going to assume (for the sake of contradiction) that lim⁡n→∞an=L\displaystyle\lim_{n\to\infty} a_n = L.

We're going to apply the same strategy: we're going to pick ε\epsilon small enough so that LL would have to be in two different places at the same time, which should give us a contradiction. Based on the picture, the distance between 2n2^n and 2n+12^{n+1} is 2n≥22^n \geq 2, so ε=1\epsilon = 1 should work again.

By definition of the limit, there exists N∈RN \in \R such that if n>Nn > N, then ∣an−L∣<1\abs{a_n - L} < 1. Notice this means that ∣an+1−L∣<1\abs{a_{n+1} - L} < 1 as well, so

2n=∣an−an+1∣≤∣an−L∣+∣an+1−L∣<1+1=2.2^n = \abs{a_n - a_{n+1}} \leq \abs{a_n - L} + \abs{a_{n+1} - L} < 1 + 1 = 2.

Thus, we get a contradiction, so the limit must not have existed to begin with.