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{ℝ}$ 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{ℝ}$ is a field (+ and · defined with certain properties)
2. There is a strict linear order $<$ on $\mathbb{ℝ}$ that makes it into an ordered field
3. (Completeness Axiom) If a nonenmpty subset $E\subset \mathbb{ℝ}$ 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 $ϵ>0$ , there exists a natural number $n$ such that $nϵ>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{\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{\mathbb{Z}}$, $\mathbb{\mathbb{Q}}$, and $\mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}}$ are countable.

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

Limit Theorems for Sequences

1. Squeeze Theorem. For a sequence $\left\{y_n\right\}$, if $\underset{n\to \mathrm{\infty }}{\lim }{x}_n=\underset{n\to \mathrm{\infty }}{\lim }{z}_n=a$, and $x_n\le y_n\le g_n$ for $n\ge N_0$, then $\underset{n\to \mathrm{\infty }}{\lim }{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{\mathbb{N}}$ such that $x_n\le y_n$ for all $n\ge N_0$, then $\underset{n\to \mathrm{\infty }}{\lim }{x}_n\le \underset{n\to \mathrm{\infty }}{\lim }{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{ℝ}$ 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 \mathrm{\infty }$ implies $f(x_n)\to f(c)$ as $n\to \mathrm{\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{ℝ}$ 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{\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{\mathbb{N}}$. Add $(k+1{)}^3$ to both sides, and

$\begin{array}{rl}\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{array}$

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{\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\ge 2$.

1. Show that ${\left\{\frac{F_{2k}}{F_{2k-1}}\right\}}_{k\in \mathbb{\mathbb{N}}}$ is increasing while ${\left\{\frac{F_{2k+1}}{F_{2k}}\right\}}_{k\in \mathbb{\mathbb{N}}}$ is decreasing.
2. Prove that $\underset{n\to \mathrm{\infty }}{\lim }\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{\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{\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,\mathrm{\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{ℝ}$, 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{\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{\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{\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 \mathrm{\infty }$. To prove that $\underset{n\to \mathrm{\infty }}{\lim }\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{array}{rl}g(x)=f(f(x))& =f(1+\frac{1}{x})\\ & =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{array}$

It follows that $g(x_{2k-1})\to g(c_1)$ and $g(x_{2k})\to g(c_2)$ as $k\to \mathrm{\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{ℝ}$ 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{\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{ℝ}$. Let $m=\inf f([a,b])$, and $M=\sup f([a,b])$. For any $n\in \mathbb{\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\le f(x)\le M$...

...

quod erat demonstrandum

Problem 4

20 pts.

Consider $f:\mathbb{ℝ}\to \mathbb{ℝ}$ 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{ℝ}\setminus \{-1,0,1\}$.

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{ℝ}\setminus \{-1,1\}$.

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

Clearly $f(x)=g(x)h(x)$ for all $x\in \mathbb{ℝ}\setminus \{-1,0,1\}$. 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{ℝ}\setminus \{-1,1\}$. Therefore $g(x)\to 1$ as $x\to 0$, $g(x)\to \frac{1}{2}$ as $x\to 1$, and $g(x)\to \pm \mathrm{\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\ne 0$ since $0<1<\frac{\pi }{2}$. It follows that $f(x)\to \pm \mathrm{\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={(\frac{\pi }{2}+2\pi n)}^{-1}$ and $y_n={(-\frac{\pi }{2}+2\pi n)}^{-1}$ for all $n\in \mathbb{\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{\mathbb{N}}$. It follows that $f(x_n)\to 1$ and $f(y_n)\to -1$ as $n\to \mathrm{\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 ${𝒫}(X)$ denote the set of all subsets of $X$. Prove that ${𝒫}(X)$ is not of the same cardinality as $X$.

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