# MATH 409 Lecture 13

« previous | Thursday, October 10, 2013 | next »

End Exam 1 content
Lecture Slides

## Review for Test

Part 1: Chapter 1 and Appendix A

• Axioms of an ordered field
• ${\displaystyle \mathbb {R} }$ is an ordered fields
• Completeness axiom
• Archimedean principle
• Principle of Mathematical Induction
• Binomial Formula (as application of induction)
• Countable and Uncountable sets.

Part 2: Chapters 2.1–2.5 and 3.1–3.4

• Limits of sequences
• Limit theorems for sequences
• Monotone sequences
• Bolzano-Weierstrass theorem
• Cauchy Sequences (i.e. convergent sequences)
• Limits of functions (one-sided, two-sided; at point, at infinity)
• Limit Theorems for functions (analogous to theorems for sequences)
• Continuity of Functions
• Extreme value and Intermediate Value theorems
• Uniform Continuity.

### Axioms of Real Numbers

3 Postulates:

1. ${\displaystyle \mathbb {R} }$ is a field (+ and · defined with certain properties)
2. There is a strict linear order ${\displaystyle <}$ on ${\displaystyle \mathbb {R} }$ that makes it into an ordered field
3. (Completeness Axiom) If a nonenmpty subset ${\displaystyle E\subset \mathbb {R} }$ is bounded above, then ${\displaystyle E}$ has a supremem. Conversely, if ${\displaystyle E}$ is bounded below, then ${\displaystyle E}$ has an infimum.

### Theorems to Know

(will need to prove one)

Archimedian Principle. For any real number ${\displaystyle \epsilon >0}$ , there exists a natural number ${\displaystyle n}$ such that ${\displaystyle n\,\epsilon >1}$.

Principle of Mathematical Induction. Let ${\displaystyle P(n)}$ be an assertion depending on a natural variable ${\displaystyle n}$. Suppose that

• ${\displaystyle P(1)}$ holds, and
• Whenever ${\displaystyle P(k)}$ holds, so does ${\displaystyle P(k+1)}$

Then ${\displaystyle P(n)}$ holds for all ${\displaystyle n\in \mathbb {N} }$.

Theorem. If ${\displaystyle A_{1}}$, ${\displaystyle A_{2}}$, ... are finite or countable sets, then the union is also finite or countable. As a consequence, ${\displaystyle \mathbb {Z} }$, ${\displaystyle \mathbb {Q} }$, and ${\displaystyle \mathbb {N} \times \mathbb {N} }$ are countable.

Theorem. ${\displaystyle \mathbb {R} }$ is uncountable.

#### Limit Theorems for Sequences

1. Squeeze Theorem. For a sequence ${\displaystyle \left\{y_{n}\right\}}$, if ${\displaystyle \lim _{n\to \infty }x_{n}=\lim _{n\to \infty }z_{n}=a}$, and ${\displaystyle x_{n}\leq y_{n}\leq g_{n}}$ for ${\displaystyle n\geq N_{0}}$, then ${\displaystyle \lim _{n\to \infty }y_{n}=a}$
2. Comparison Theorem. if ${\displaystyle \left\{x_{n}\right\}}$ and ${\displaystyle \left\{y_{n}\right\}}$ are convergent sequences, and there exists ${\displaystyle N_{0}\in \mathbb {N} }$ such that ${\displaystyle x_{n}\leq y_{n}}$ for all ${\displaystyle n\geq N_{0}}$, then ${\displaystyle \lim _{n\to \infty }x_{n}\leq \lim _{n\to \infty }y_{n}}$
3. Arithmetic Operations Theorems. Limit of sum/difference is sum/difference of limits; Limit of product/quotient (for nonzero denominator) is product/quotient of limits

Monotone Convergence Theorem. Any monotone sequence converges to a limit if bounded, and diverges to infinity otherwise.

Bolzano-Weierstrass. Every bounded sequence of real numbers has a convergent subsequence.

Cauchy Sequences. Any Cauchy sequence is convergent.

#### Limit Theorems for Functions

Sequential Characterization of Continuity. ${\displaystyle f:E\to \mathbb {R} }$ is continuous at ${\displaystyle c\in E}$ if and only if for any sequence ${\displaystyle \left\{x_{n}\right\}}$ of elements of ${\displaystyle E}$, ${\displaystyle x_{n}\to c}$ as ${\displaystyle n\to \infty }$ implies ${\displaystyle f(x_{n})\to f(c)}$ as ${\displaystyle n\to \infty }$.

Arithmetic Operations Theorems. (analogous to above)

Extreme Value Theorem. If ${\displaystyle I=[a,b]}$ is a closed, bounded interval, then any continuous function ${\displaystyle f:I\to \mathbb {R} }$ is bounded and attains its max and min within ${\displaystyle I}$.

Intermediate Value Theorem.

Theorem. Any function continuous on a closed bounded interval [a,b] is also uniformly continuous on [a,b]

## Sample Test

### Problem 1

15 pts.

Prove that for any ${\displaystyle n\in \mathbb {N} }$,

${\displaystyle 1^{3}+2^{3}+3^{3}+\dots +n^{3}={\frac {n^{2}(n+1)^{2}}{4}}\,\!}$

Application of principle of mathematical induction

Proof. Let ${\displaystyle n=1}$, then ${\displaystyle 1=1}$. Assume that ${\displaystyle \sum _{k=1}^{n}k^{3}={\frac {n^{2}(n+1)}{4}}}$ holds for some ${\displaystyle n\in \mathbb {N} }$. Add ${\displaystyle (k+1)^{3}}$ to both sides, and

{\displaystyle {\begin{aligned}\sum _{k=1}^{n+1}k^{3}&={\frac {k^{2}(k+1)^{2}}{4}}+(k+1)^{3}\\&=(k+1)^{2}\,{\frac {k^{2}+4(k+1)}{4}}\\&={\frac {(k+1)^{2}\,(k+2)^{2}}{4}}\end{aligned}}}

quod erat demonstrandum

Note, we have just proved that ${\displaystyle \sum _{k=0}^{n}k^{3}={\frac {n^{2}(n+1)^{2}}{4}}}$. It is also known that ${\displaystyle \sum _{k=0}^{n}k={\frac {n(n+1)}{2}}}$. Therefore ${\displaystyle \sum _{k=0}^{n}k^{3}=\left(\sum _{k=1}^{n}k\right)^{2}}$ for all ${\displaystyle n\in \mathbb {N} }$.

### Problem 2

30 pts.

Let ${\displaystyle \left\{F_{n}\right\}}$ be the sequence of Fibonacci numbers ${\displaystyle F_{1}=F_{2}=1}$ and ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$ for ${\displaystyle n\geq 2}$.

1. Show that ${\displaystyle \left\{{\frac {F_{2k}}{F_{2k-1}}}\right\}_{k\in \mathbb {N} }}$ is increasing while ${\displaystyle \left\{{\frac {F_{2k+1}}{F_{2k}}}\right\}_{k\in \mathbb {N} }}$ is decreasing.
2. Prove that ${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}={\frac {{\sqrt {5}}+1}{2}}}$.

Proof of 1. Let ${\displaystyle x_{n}={\frac {F_{n+1}}{F_{n}}}}$ for ${\displaystyle n\in \mathbb {N} }$. Then

${\displaystyle x_{n+1}={\frac {F_{n+2}}{F_{n+1}}}={\frac {F_{n}+F_{n+1}}{F_{x+1}}}=1+{\frac {1}{x_{n}}}}$

for all ${\displaystyle n\in \mathbb {N} }$. In particular, ${\displaystyle x_{1}=1}$, ${\displaystyle x_{2}=1+{\frac {1}{x_{1}}}=2}$, and ${\displaystyle x_{3}=1+{\frac {1}{x_{2}}}={\frac {3}{2}}}$, and ${\displaystyle x_{4}=1+{\frac {1}{x_{3}}}={\frac {5}{3}}}$. Notice that

${\displaystyle x_{1}

The function ${\displaystyle f(x)=1+{\frac {1}{x}}}$ is strictly decreasing on the interval ${\displaystyle (0,\infty )}$ and maps it to itself. Therefore its second iteration ${\displaystyle g=f\circ f}$ is strictly increasing on ${\displaystyle I}$ and ${\displaystyle g(I)\subset I}$ (a decreasing function reverses the order of ${\displaystyle \mathbb {R} }$, so applying a decreasing function to a decreasing function once again reverses the order to be increasing). We have ${\displaystyle x_{n+2}=f(x_{n+1})=f(f(x_{n}))=g(x_{n})}$ for ${\displaystyle n\in \mathbb {N} }$. Now it follows by induction on ${\displaystyle k}$ that

${\displaystyle x_{2k-1} for all ${\displaystyle k\in \mathbb {N} }$

(apply ${\displaystyle g}$ to all elements of the inequality for the inductive step).

The proposition holds by transitivity and comparison theorem.

quod erat demonstrandum

Proof of 2. We already know that ${\displaystyle x_{n}={\frac {F_{n+1}}{F_{n}}}}$ satisfy inequalities

${\displaystyle x_{2k-1} for all ${\displaystyle k\in \mathbb {N} }$

It follows that ${\displaystyle \left\{x_{2k-1}\right\}}$ is strictly increasing, ${\displaystyle \left\{x_{2k}\right\}}$ is strictly decreasing, and both sequences are bounded. Therefore, these sequences are converging to some positive limits: ${\displaystyle x_{2k-1}\to c_{1}}$ and ${\displaystyle x_{2k}\to c_{2}}$ as ${\displaystyle k\to \infty }$. To prove that ${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}={\frac {{\sqrt {5}}+1}{2}}}$, it is enough to show that ${\displaystyle c_{1}=c_{2}={\frac {{\sqrt {5}}+1}{2}}}$.

For any ${\displaystyle x>0}$ we obtain

{\displaystyle {\begin{aligned}g(x)=f(f(x))&=f\left(1+{\frac {1}{x}}\right)\\&=1+{\frac {1}{1+{\frac {1}{x}}}}\\&=1+{\frac {1}{\frac {x+1}{x}}}\\&=1+{\frac {x}{x+1}}\\&={\frac {2x+1}{x+1}}\end{aligned}}}

It follows that ${\displaystyle g(x_{2k-1})\to g(c_{1})}$ and ${\displaystyle g(x_{2k})\to g(c_{2})}$ as ${\displaystyle k\to \infty }$. However, ${\displaystyle g(x_{2k-1}=x_{2k+1}}$ and ${\displaystyle g(x_{2k})=x_{2k+2}}$, which implies that ${\displaystyle g(c_{1})=c_{1}}$ and ${\displaystyle g(c_{2})=c_{2}}$. Since

${\displaystyle x-g(x)={\frac {x(x+1)}{x+1}}-{\frac {2x+1}{x+1}}={\frac {x^{2}-x-1}{x+1}}\,\!}$

Therefore ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$ are roots of the equation ${\displaystyle x^{2}-x-1=0}$. There are two roots because the constant is negative. Moreover, both roots must be of different signs (leading coefficient is positive, and constant is negative). This equation has two roots, ${\displaystyle {\frac {1\pm {\sqrt {5}}}{2}}}$. One of the roots is negative, so ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$ are equal to the other root, ${\displaystyle {\frac {{\sqrt {5}}+1}{2}}}$.

quod erat demonstrandum

### Problem 3

Prove the extreme value theorem: If ${\displaystyle f:[a,b]\to \mathbb {R} }$ is a continuous function on a closed bounded interval ${\displaystyle [a,b]}$, then ${\displaystyle f}$ is bounded and attains its extreme values on ${\displaystyle [a,b]}$.

Proof. First let us prove that ${\displaystyle f}$ is bounded. Assume the contrary. Then for every ${\displaystyle n\in \mathbb {N} }$, there exists a point ${\displaystyle x_{n}\in [a,b]}$ such that ${\displaystyle |f(x_{n})|>n}$. We obtain a sequence ${\displaystyle \left\{x_{n}\right\}}$.

...

Since ${\displaystyle f}$ is bounded, the image ${\displaystyle f([a,b])}$ is a bounded subset of ${\displaystyle \mathbb {R} }$. Let ${\displaystyle m=\inf f([a,b])}$, and ${\displaystyle M=\sup f([a,b])}$. For any ${\displaystyle n\in \mathbb {N} }$, the number ${\displaystyle M-{\frac {1}{n}}}$ is not an upper bound of ${\displaystyle f([a,b])}$ and ${\displaystyle m+{\frac {1}{n}}}$ is not a lower bound of ${\displaystyle f([a,b])}$. Hence we can find points ${\displaystyle y_{n},z_{n}\in [a,b]}$ such that ${\displaystyle f(y_{n})>M-{\frac {1}{n}}}$ and ${\displaystyle f(z_{n}). At the same time, ${\displaystyle m\leq f(x)\leq M}$...

...

quod erat demonstrandum

### Problem 4

20 pts.

Consider ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$ defined by

${\displaystyle f(-1)=f(0)=f(1)=0}$ and ${\displaystyle f(x)={\frac {x-1}{x^{2}-1}}\,\sin {\left({\frac {1}{x}}\right)}}$ for ${\displaystyle x\in \mathbb {R} \setminus \left\{-1,0,1\right\}}$.

1. determine all points at which the function ${\displaystyle f}$ is continuous.
2. Is the function ${\displaystyle f}$ uniformly continuous on the interval ${\displaystyle (0,1)}$? is it uniformly continuous on the interval ${\displaystyle (0,2)}$?

Proof of 1. The polynomial functions ${\displaystyle g_{1}(x)=x-1}$ and ${\displaystyle g_{2}(x)=x^{2}-1}$ are continuous on the entire real line. Moreover, ${\displaystyle g_{2}(x)=0}$ if and only if ${\displaystyle x=\pm 1}$. Therefore the quotient ${\displaystyle g(x)={\frac {g_{1}(x)}{g_{2}(x)}}}$ is well-defined and continuous on ${\displaystyle \mathbb {R} \setminus \left\{-1,1\right\}}$.

Further, the function ${\displaystyle h_{1}(x)={\frac {1}{x}}}$ is continuous on ${\displaystyle \mathbb {R} \setminus \left\{0\right\}}$. Since ${\displaystyle \sin {x}}$ is continuous on ${\displaystyle \mathbb {R} }$, the composite function ${\displaystyle h(x)=h_{2}(h_{1}(x))}$ is continuous on ${\displaystyle \mathbb {R} \setminus \left\{0\right\}}$.

Clearly ${\displaystyle f(x)=g(x)\,h(x)}$ for all ${\displaystyle x\in \mathbb {R} \setminus \left\{-1,0,1\right\}}$. It follows that ${\displaystyle f}$ is continuous on that range as well.

It remains to determine whether the function ${\displaystyle f}$ is continuous at points ${\displaystyle -1}$, ${\displaystyle 0}$, and ${\displaystyle 1}$. Observe that ${\displaystyle g(x)={\frac {1}{x+1}}}$ for all ${\displaystyle x\in \mathbb {R} \setminus \left\{-1,1\right\}}$. Therefore ${\displaystyle g(x)\to 1}$ as ${\displaystyle x\to 0}$, ${\displaystyle g(x)\to {\frac {1}{2}}}$ as ${\displaystyle x\to 1}$, and ${\displaystyle g(x)\to \pm \infty }$ as ${\displaystyle x\to -1}$.

Since the function ${\displaystyle h}$ is continuous at ${\displaystyle -1}$ and ${\displaystyle 1}$, we have ${\displaystyle h(x)\to -1=-\sin {1}}$ as ${\displaystyle x\to -1}$ and ${\displaystyle h(x)\to h(1)=\sin {1}}$ as ${\displaystyle x\to 1}$. Note that ${\displaystyle \sin {1}\neq 0}$ since ${\displaystyle 0<1<{\frac {\pi }{2}}}$. It follows that ${\displaystyle f(x)\to \pm \infty }$ as ${\displaystyle x\to -1}$. In particular ${\displaystyle f}$ is discontinuous at ${\displaystyle -1}$.

Further, ${\displaystyle f(x)\to {\frac {1}{2}}\,\sin {1}}$ as ${\displaystyle x\to 1}$. Since ${\displaystyle f(1)=0}$, the function ${\displaystyle f}$ has a removable discontinuity at ${\displaystyle 1}$.

All that remains is continuity at ${\displaystyle 0}$. Finally, ${\displaystyle f}$ is not continuous at ${\displaystyle 0}$ since it has no limit at ${\displaystyle 0}$. To be precise, let ${\displaystyle x_{n}=\left({\frac {\pi }{2}}+2\pi n\right)^{-1}}$ and ${\displaystyle y_{n}=\left(-{\frac {\pi }{2}}+2\pi n\right)^{-1}}$ for all ${\displaystyle n\in \mathbb {N} }$. Then ${\displaystyle \left\{x_{n}\right\}}$ and ${\displaystyle \left\{y_{n}\right\}}$ are two convergent sequences of positive numbers converging to 0. We have ${\displaystyle h(x_{n})=1}$ and ${\displaystyle h(y_{n})=-1}$ for all ${\displaystyle n\in \mathbb {N} }$. It follows that ${\displaystyle f(x_{n})\to 1}$ and ${\displaystyle f(y_{n})\to -1}$ as ${\displaystyle n\to \infty }$. Hence there is no limit of ${\displaystyle f}$ as ${\displaystyle x\to 0^{+}}$.

quod erat demonstrandum

Proof of 2. Any function uniformly continuous on the open interval ${\displaystyle (0,1)}$ can be extended to a continuous function on ${\displaystyle [0,1]}$. As a consequence, such a function has a right-hand limit at ${\displaystyle 0}$. However, we already know that ${\displaystyle f}$ has no right-hand limit at ${\displaystyle 0}$. Therefore ${\displaystyle f}$ is not uniformly continuous on ${\displaystyle (0,1)}$ (due to oscillation to the right of 0)

The function ${\displaystyle f}$ is continuous at ${\displaystyle (1,2]}$ and has a removable singularity at ${\displaystyle 1}$. Changing the value of ${\displaystyle f}$ at ${\displaystyle 1}$ to the limit at ${\displaystyle 1}$, we obtain a function continuous on ${\displaystyle [1,2]}$. It is known that every function continuous on the closed interval ${\displaystyle [1,2]}$ is also uniformly continuous on ${\displaystyle [1,2]}$. Further, any function uniformly continuous on the set ${\displaystyle [1,2]}$ is also uniformly continuous on its subset ${\displaystyle (1,2)}$. Since the redefined function coincides with ${\displaystyle f}$ on ${\displaystyle (1,2)}$, we conclude that ${\displaystyle f}$ is uniformly continuous on ${\displaystyle (1,2)}$

The function ${\displaystyle f}$ is continuous at ${\displaystyle (1,2]}$ and has a removable singularity at ${\displaystyle 1}$. Changing the value of ${\displaystyle f}$ at ${\displaystyle 1}$ to the limit at ${\displaystyle 1}$, we obtain a function continuous on ${\displaystyle [1,2]}$. It is known that every function continuous on the closed interval ${\displaystyle [1,2]}$ is also uniformly continuous on ${\displaystyle [1,2]}$. Further, any function uniformly continuous on the set ${\displaystyle [1,2]}$ is also uniformly continuous on its subset ${\displaystyle (1,2)}$. Since the redefined function coincides with ${\displaystyle f}$ on ${\displaystyle (1,2)}$, we conclude that ${\displaystyle f}$ is uniformly continuous on ${\displaystyle (1,2)}$.

quod erat demonstrandum

### Bonus Problem 5

Given a set ${\displaystyle X}$, let ${\displaystyle {\mathcal {P}}(X)}$ denote the set of all subsets of ${\displaystyle X}$. Prove that ${\displaystyle {\mathcal {P}}(X)}$ is not of the same cardinality as ${\displaystyle X}$.

(paradox: is set of all sets countable? Well, introduce concept of class)