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

Theorems to Know

(will need to prove one)

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

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

• $P(1)$ holds, and
• Whenever $P(k)$ holds, so does $P(k+1)$

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

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

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

Limit Theorems for Sequences

1. Squeeze Theorem. For a sequence $\left\{y_{n}\right\}$, if $\lim _{n\to \infty }x_{n}=\lim _{n\to \infty }z_{n}=a$, and $x_{n}\leq y_{n}\leq g_{n}$ for $n\geq N_{0}$, then $\lim _{n\to \infty }y_{n}=a$
2. Comparison Theorem. if $\left\{x_{n}\right\}$ and $\left\{y_{n}\right\}$ are convergent sequences, and there exists $N_{0}\in \mathbb {N}$ such that $x_{n}\leq y_{n}$ for all $n\geq N_{0}$, then $\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. $f:E\to \mathbb {R}$ is continuous at $c\in E$ if and only if for any sequence $\left\{x_{n}\right\}$ of elements of $E$, $x_{n}\to c$ as $n\to \infty$ implies $f(x_{n})\to f(c)$ as $n\to \infty$.

Arithmetic Operations Theorems. (analogous to above)

Extreme Value Theorem. If $I=[a,b]$ is a closed, bounded interval, then any continuous function $f:I\to \mathbb {R}$ is bounded and attains its max and min within $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 $n\in \mathbb {N}$,

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

Application of principle of mathematical induction

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

${\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 $\sum _{k=0}^{n}k^{3}={\frac {n^{2}(n+1)^{2}}{4}}$. It is also known that $\sum _{k=0}^{n}k={\frac {n(n+1)}{2}}$. Therefore $\sum _{k=0}^{n}k^{3}=\left(\sum _{k=1}^{n}k\right)^{2}$ for all $n\in \mathbb {N}$.

Problem 2

30 pts.

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

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

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

$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 $n\in \mathbb {N}$. In particular, $x_{1}=1$, $x_{2}=1+{\frac {1}{x_{1}}}=2$, and $x_{3}=1+{\frac {1}{x_{2}}}={\frac {3}{2}}$, and $x_{4}=1+{\frac {1}{x_{3}}}={\frac {5}{3}}$. Notice that

$x_{1}<x_{3}<x_{4}<x_{2}\,\!$

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

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

(apply $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 $x_{n}={\frac {F_{n+1}}{F_{n}}}$ satisfy inequalities

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

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

For any $x>0$ we obtain

${\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 $g(x_{2k-1})\to g(c_{1})$ and $g(x_{2k})\to g(c_{2})$ as $k\to \infty$. However, $g(x_{2k-1}=x_{2k+1}$ and $g(x_{2k})=x_{2k+2}$, which implies that $g(c_{1})=c_{1}$ and $g(c_{2})=c_{2}$. Since

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

Therefore $c_{1}$ and $c_{2}$ are roots of the equation $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, ${\frac {1\pm {\sqrt {5}}}{2}}$. One of the roots is negative, so $c_{1}$ and $c_{2}$ are equal to the other root, ${\frac {{\sqrt {5}}+1}{2}}$.

quod erat demonstrandum

Problem 3

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

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

...

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

...

quod erat demonstrandum

Problem 4

20 pts.

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

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

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

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

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

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

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

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

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

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

quod erat demonstrandum

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

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

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

quod erat demonstrandum

Bonus Problem 5

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

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