\( \newcommand{\d}{\delta} \newcommand{\e}{\varepsilon} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\card}[1]{\text{card}(#1)} \newcommand{\lub}{\text{lub }} \newcommand{\glb}{\text{glb }} \newcommand{\powerset}[1]{\mathcal{P}\left(#1\right)} \newcommand{\B}[2]{(#1-#2,#1+#2)} \)
Feb 23

Here is a solution for Problem 17.

Suppose it is contractive. Then there is a \(c\in(0,1)\) such that for all \(n\in\N\), \[ 1>c>\left|\frac{a_{n+2}-a_{n+1}}{a_{n+1}-a_n}\right|=\frac{n}{n+2}\to1. \] The Sandwich Theorem (3.9) implies \(c=1\). This contradiction forces the conclusion that \(a_n\) cannot be contractive.

Here is a solution for Problem 18.

By Theorem 3.22, \(a_n\) converges to some \(A\in\R\). Theorem 3.14 implies \(A=L\).

Problem 20. (Due Mar 2.) Let \(x_n\) be a sequence with range \(\{0,1,2,3,4,5,6,7,8,9\}\). Prove that \(\sum_{n=1}^\infty x_n10^{-n}\) converges and its sum is in the interval \([0,1]\).

Problem 21. (Due Mar 2.) Prove that \(6.17272727272\cdots\) is a rational number.

Feb 21

Here is a solution for Problem 16.

To see \(a_n\) is bounded, note that for every \(n\in\N\), \[ \frac{1}{2} = \frac{n}{2n} \lt \sum_{k=n+1}^{2n}1/k=a_n \lt \frac{n}{n+1} \lt 1. \] Then \begin{align*} a_{n+1}-a_n &= \sum_{k=n+2}^{2(n+1)}\frac{1}{k}-\sum_{k=n+1}^{2n}\frac{1}{k}\\ &= \frac{1}{2n+2}+\frac{1}{2n+1}-\frac{1}{n+1}\\ &= \frac{1}{4n^2+6n+2}\\ &>0 \end{align*} shows \(a_n\) is increasing. Theorem 3.11 implies \(a_n\) converges. Theorem 3.22 now implies \(a_n\) is a Cauchy sequence.

Here is a solution for Extra Credit 3.

By using upper and lower rectangles on the graph of \(y=1/x\), it can be seen that \[ a_n+\frac{1}{n} > \int_{n+1}^{2n}\frac{dx}{x} > a_n. \] (See the figure below for the case when \(n=6\).) Calculate the integral and rearrange this inequality. \[ \frac{1}{n} > \ln\left( \frac{2n}{n+1} \right)-a_n > 0. \] The Sandwich Theorem (3.9) implies \(a_n\to\ln2\).

sliding harmonic sum

Feb 19

Problem 19. (Due Feb 26.) If \(a_n\) is a convergent sequence and \(b_n\) is a sequence such that \(|a_m-a_n|\ge|b_m-b_n|\) for all \(m,n\in\N\), then \(b_n\) converges.

Here is a solution for Problem 15.

Since \(a_n\) is bounded, there is an interval \(J=[\alpha,\beta]\) such that \(\{n:a_n\in J\}=\N\). Let \(\e>0\) choose \(N\in\N\) such that \[\frac{\beta-\alpha}{N}\lt\e.\] Partition \(J\) by \(\alpha=x_0\lt x_1\lt\cdots\lt x_N=\beta\), where \(x_i-x_{i-1}=(\beta-\alpha)/N\) for \(1\le i\le N\). If \(S_i=\{n:x_{i-1}\le a_n\le x_i\}\) for \(1\le i\le N\), then \(\N=\bigcup_{i=1}^N S_i\). At least one of the \(S_i\), say \(S_{i_0}\) must be infinite, else \(\N\) is a finite union of finite sets. Let \(I\) be any interval of length \(\e\) containing \([x_{i_0-1},x_{i_0}]\).

If \(a_n=n\), then no interval of finite length can contain an infinite number of terms from the sequence, so the boundedness of the sequence is necessary.

Feb 17

Here is a solution for Problem 14.

First, it will be shown \(a_n\gt1\)for all \(n\in\N\).

It is clear that \(a_1=3\gt1\). Suppose \(a_n>1\) for some \(n\). Then \[ a_{n+1}=2-\frac{1}{a_n}>2-1=1, \] and it follows by induction that \(a_n>1\) for all \(n\in\N\).

Next, it will be shown that \(a_n\) is strictly decreasing.

Clearly \(a_1=3>5/3=a_2\). Suppose \(a_n\lt a_{n-1}\) for some \(n>1\). Then \begin{align*} a_{n+1}-a_n &= 2-\frac{1}{a_n}-a_n\\ &= 2-\frac{1}{a_n}-\left( 2-\frac{1}{a_{n-1}} \right)\\ &=\frac{1}{a_{n-1}}-\frac{1}{a_n}\\ &= \frac{a_n-a_{n-1}}{a_{n-1}a_n}\\ &\lt 0 \end{align*} In the last step, the induction hypothesis was invoked, along with the facts that \(a_{n-1}>a_n>1>0\). It follows by induction that \(a_n\) is a strictly decreasing sequence bounded below by \(1\).

Theorem 3.11 implies \(a_n\to\ell\) for some \(\ell\ge1\). Using this \begin{align*} \lim_{n\to\infty}a_{n+1}&=\lim_{n\to\infty}\left( 2-\frac{1}{a_n} \right)\\ \ell&=2-\frac{1}{\ell}\\ \ell^2-2\ell+1&=0\\ (\ell-1)^2&=0\\ \ell&=1 \end{align*}

Feb 16

Problem 17. (Due Feb 23.) \(a_n=1/n\) is a Cauchy sequence which is not contractive.

Problem 18. (Due Feb 23.) If \(a_n\) is a Cauchy sequence and \(b_n\) is a subsequence of \(a_n\) such that \(b_n\to L\), then \(a_n\to L\).

Feb 14 💕

Problem 16. (Due Feb 21.) Prove that \(a_n=\sum_{k=n+1}^{2n}\frac{1}{k}\) is a Cauchy sequence.

Extra Credit 3. (Due Feb 21.) Find \( \lim_{n\to\infty}\sum_{k=n+1}^{2n}\frac{1}{k}\). (You will probably have to use some calculus.)

Here is a solution for Extra Credit 2.

Note first that \((2n)!\ge\prod_{k=n}^{2n}k> n^{n+1}\). Therefore \[ \sqrt[2n]{(2n)!}>\sqrt[2n]{n^{n+1}}\ge\sqrt{n}. \] Next, since \((2n+1)!\ge\prod_{k=n}^{2n+1}k>\prod_{k=n}^{2n}k> n^{n+1}\), \[ \sqrt[2n+1]{(2n+1)!}>\sqrt[2n+1]{n^{n+1}}\ge\sqrt{n}. \] Therefore, \(a_n\ge\sqrt{n}\to\infty\), and the proof is done.

For a nice application of this limit, see the article by Charles C. Mumma, \(n!\) and The Root Test, Amer. Math. Monthly, 93(7):561, August-September 1986.

Feb 13

Here is a solution for Problem 10.

Let \(p=q/r\), where \(q,r\in\Z\). \begin{align*} q+x\in\Q &\iff \exists m,n\in\Z\left( \frac{q}{r}+x=\frac{m}{n} \right)\\ &\iff \exists m,n\in\Z\left( x=\frac{m}{n}-\frac{q}{r}=\frac{mr-nq}{nr} \right)\\ &\iff x\in\Q \end{align*}

Here is a solution for Problem 11.

First note that if \(A=\emptyset\), then \(B=\R\) and \(\lub A=\glb B=-\infty\). Also, if \(A\) is not bounded above, then \(B=\emptyset\) and \(\lub A=\glb B=\infty\).

So, suppose \(A\ne\emptyset\ne B\) and \(A\) is bounded above. Let \(\alpha=\lub A\) and \(\beta=\glb B\). Since \(\alpha\) is an upper bound for \(A\), it follows that \(\alpha\in B\). This, in turn, implies \(\beta\le\alpha\).

Suppose \(\beta\lt\alpha\) and \(\e=(\alpha-\beta)/2\). According to Theorem 2.19, there is a \(\gamma\in(\alpha-\e,\alpha]\cap A\) and a \(\delta\in[\beta,\beta+\e)\cap B\). So, \(\delta\lt\gamma\), where \(\delta\) is an upper bound for \(A\) and \(\gamma\in A\). This is clearly impossible, and we must conclude \(\alpha=\beta\), as desired.

Here is a solution for Problem 12.

Clearly, \(\sigma(1)\ge1\). Suppose \(\sigma(n)\ge n\) for some \(n\in\N\). Then, \(\sigma(n+1)>\sigma(n)\ge n\), implies \(\sigma(n+1)\ge n+1\). By induction, it follows that \(\sigma(n)\ge n,\ \forall n\in\N\).

Here is a solution for Problem 13.

Let \(\e>0\) and \(N\in\N\) such that \(N>11/9\e\). If \(n\ge N\), then \begin{align*} \left|a_n-2\right| &= \left|\frac{4n-1}{3n+2}-\frac{4}{3}\right|\\ &= \frac{11}{3(3n+2)}\\ &\le \frac{11}{3(3N+2)}\\ &\lt \frac{11}{3\left(3\frac{11}{9\e}+2\right)}\\ &= \frac{11}{\frac{11}{\e}+6}\\ &\lt \frac{11}{\frac{11}{\e}}\\ &= \e. \end{align*} This shows Definition 3.3 is satisfied, so \(a_n\to4/3\).

Feb 12

Problem 15. (Due Feb 19.) Let \(a_n\) be a bounded sequence. Prove that given any \(\e>0\), there is an interval \(I\) with length \(\e\) such that \(\{n:a_n\in I\}\) is infinite. Is it necessary that \(a_n\) be bounded?

Here is a solution for Problem 9.

Let \(I=(a,b).\)

First, assume \(a>0\). According to Corollary 2.23(b), there is an \(n\in\N\) such that \(1/n\lt b-a\). Corollary 2.23(a) shows \(\{k\in\N:k>an\}\ne\emptyset\). Let \(m=\min\{k\in\N:k>an\}\), so \(m/n>a\). In order to arrive at a contradiction, suppose\(m/n\ge b\). Then \[ \frac{m-1}{n}=\frac{m}{n}-\frac{1}{n}\ge b-\frac{1}{n}>b-(b-a)=a \] is a contradiction of the choice of \(m\) and it must be that \(m/n\lt b\).

Therefore \(m/n\in(a,b)\).

If \(a\lt 0\), then use the Archimedean property to find an \(N\in\N\) such that \(N>-a\). From above, there is a \(q\in(a+N,b+N)\cap\Q\). Clearly, \(q-N\in(a,b)\cap\Q\) because \(\Q\) is closed under addition.

Feb 9

Problem 14. (Due Feb 16.) Let \(a_1=3\) and \(a_{n+1}=2-1/a_n\) for \(n\in\N\). Analyze the sequence.

Feb 7

Extra Credit 2. (Due Valentine’s Day.) Determine the limit of \(a_{n}=\sqrt[n]{n!}\). (Hint: If \(n\) is even, then show that \(n!>(n/2)^{n/2}\).)

Feb 5

Here is a solution for Problem 8.

Since \(\alpha\) is an upper bound for \(S\), \((\alpha,\infty)\cap S=\emptyset \). Because \(\alpha\in S \), it follows that for all \(\e>0 \), \(\alpha\in(\alpha-\e,\alpha]\cap S \), so \((\alpha-\e,\alpha]\cap S\ne\emptyset \). Theorem 2.19 implies \(\alpha=\lub{S} \).

Here is a solution for Problem 7.

By assumption, \(a\ge0\). Assume \(a>0\). The given condition gives \(a>a\ge0\), which is impossible. This contradiction forces the conclusion \(a=0\).

Feb 1

Problem 12. (Due Feb 12.) If \(\sigma:\N\to\N\) is strictly increasing, then \(\sigma(n)\ge n\) for all \(n\in\N\).

Problem 13. (Due Feb 12.) Let the sequence \(\displaystyle a_n=\frac{4n-1}{3n+2}\). Use the definition of convergence for a sequence to show \(a_n\) converges.

Here is a solution for Problem 6.

Case 1: Suppose \(a\) and \(b\) are negative. Then \(-a\) and \(-b\) are positive and \((-a)(-b)=ab=c\). The two-out-of-three rule implies \(c\gt0\).
Case 2: Suppose \(a\) and \(c\) are negative. Corollary 2.8 shows \(a^{-1}\lt0\). Since \(ab=c\iff b=ca^{-1}\) and case 1 implies \(b>0\).
Case 3: If \(b\) and \(c\) are negative, this is the same as case 2.

Jan 31

Problem 10. (Due Feb 9.) Let \(q\in\mathbb{Q}\) and \(x\in\R\) Prove \[ q+x\in\Q \iff x\in\Q. \]

Problem 11. (Due Feb 9.) If \(A\subset\R\) and \(B=\{x:x\text{ is an upper bound for }A\}\), then \(\lub(A)=\glb(B)\).

Jan 30

Here is a solution for Problem 5.

(\(\Rightarrow\)) Suppose\(|x|\le y\). By Theorem 2.11(a), \(|x|\ge0\) for all \(x\), so Theorem 2.5(b) shows \(y\ge0\), and consequently \(-y\le0\) by Axiom 7(b). If \(x\ge0\), then Theorem 2.11(b) implies \begin{equation}\label{ineqp5.1} -y\le0\le x\le y. \tag{3} \end{equation} If \(x\lt0\), then \(-x=|x|>0\). Multiplying the assumed inequality \(-x=|x|\le y\) by \(-1\) gives \begin{equation}\label{ineqp5.2} -y\le x\lt0\le y. \tag{4} \end{equation} Combining (3) and (4) gives \(-y\le x\le y\), as desired.

(\(\Leftarrow\)) Assume \(-y\le x\le y\). If \(x\ge0\), then \(|x|=x\), and it is obvious \(|x|\le y\). If \(x\lt0\), then multiplying the inequality \(-y\le x\) by \(-1\) gives \(-x=|x|\le y\), as desired. Therefore, in all cases, \(|x|\le y\).

Jan 29

Problem 9. (Due Feb 7.) If \(I\) is an interval, then \(\Q\cap I\ne\emptyset\).

Jan 28

Here is a solution for Problem 4.

By Axiom 4, \(1\ne0\). Apply Theorem 2.4.

Here is a solution for Problem 3.

Since \(A\subset A\cup B\), it's clear that \begin{align}\label{p3.1} \aleph_0\le\card{A}\le\card{A\cup B}.\tag{1} \end{align} By assumption, there are two bijections \(\phi:A\to\N\) and \(\psi:B\to\N\). Define \(\zeta:A\cup B\to\N\) by \begin{align*} \zeta(x) = \begin{cases} 2\phi(x), & x\in (A\setminus B) \cup (A\cap B)\\ 2\psi(x)-1, & x\in B\setminus A \end{cases} \end{align*} It is straightforward to show \(\zeta\) is injective. This implies \[ \card{A\cup B}\le\aleph_0.\tag{2} \] Combining (1) and (2) shows \(\card{A\cup B}=\aleph_0\).

Jan 26

Problem 7. (Due Feb 5.) If \(\F\) is an ordered field and \(a\in\F\) such that \(0\le a\lt \e\) for every \(\e\gt0\), then \(a=0\).

Problem 8. (Due Feb 2.) If \(\alpha\) is an upper bound for \(S\) and \(\alpha\in S\), then \(\alpha=\lub S\).

Jan 24

Problem 6. (Due Jan 31.) Let \(\F\) be an ordered field and \(a,b,c\in\F\). If \(ab=c\) and two of \(a\), \(b\) and \(c\) are negative, then the third is positive.

Jan 22

Problem 5. (Due Jan 29.) Prove Theorem 2.11(d) from the notes.

Jan 21

Here is a solution for Extra Credit 1.

One way to do this is to figure out the first few sets in the sequences \(A_n\) and \(B_n\). \begin{align*} &B_1=\Z\setminus f(\N)=\Z\setminus\N=\{-n:n\in\omega\}=\{0,-1,-2,-3,\dots\}\\ % &A_1=g(B_1)=\{g(-n):n\in\omega\}=\{1+3n:n\in\omega\}=\{1,4,7,10,\dots\}\\ % &B_2=A_1\\ % &A_2=g(B_2) = \{g(1+3n):n\in\omega\} = \{2+9n:n\in\omega\} = \{2,11,20,29,\dots\}\\ % &B_3=A_2\\ % &A_3=g(B_3) =\{g(2+9n):n\in\omega\} =\{5+27n:n\in\omega\} =\{5,32,59,86,\dots\}\\ % &B_4=A_3\\ % &A_4 =g(B_4) =\{g(5+27n):n\in\omega\} =\{14+81n:n\in\omega\} =\{14,95,176,\dots\}\\ \end{align*} Since all elements of \(A_n\) for \(n>3\) exceed \(6\), it follows that \(7\in\tilde{A}\) and \(6\in A\setminus\tilde{A}\). Therefore, \(h(7)=g^{-1}(7)=-2\) and \(h(6)=f(6)=6\).

It's an interesting puzzle to determine the form of \(A_k\) for an arbitrary \(k\). It turns out that \[ A_1=\{1+3n:n\in\omega\} \] and for \(k>1\), \[ A_k=\left\{1+\sum_{i=1}^{k-1}3^{i-1}+3^kn:n\in\omega\right\} =\left\{3^k\left(n+\frac{1}{2}\right)+\frac{1}{2}:n\in\omega\right\}. \]

I've not been able to find a satisfying formula giving the elements of \(\tilde{A}\).

Here is a solution for Problem 2.

It must be shown that \(g\circ f\) is surjective and injective.

Let \(z\in C\). Since \(g\) is surjective, there is a \(y\in B\) such that \(g(y)=z\) and since \(f\) is surjective, there is an \(x\in A\) such that \(f(x)=y\). Since, \(g\circ f(x)=g(y)=z\) and \(z\) is an arbitrary element of \(C\), it follows that \(g\circ f\) is surjective.

If \(x_1,x_2\in A\) with \(x_1\ne x_2\), then \(f(x_1)\ne f(x_2)\) because \(f\) is injective. In the same way, since \(g\) is injective, \(g(f(x_1))\ne g(f(x_2))\) and it follows that \(g\circ f\) is injective.

Jan 19

Chapter 1 was finished and the first seven axioms of \(\R\) were introduced.

Problem 3. (Due Jan 26) If \(A\) and \(B\) are sets such that \(\card{A}=\card{B}=\aleph_0\), then \(\card{A\cup B}=\aleph_0\).

Problem 4. (Due Jan 26) In an ordered field \(\F\) show \(0\lt1\).

Jan 17

To solve Problem 1, let \(S=\{a,\{a\}\}\)

for some \(a\). Then \[ S\cap\powerset{S}=\{a,\{a\}\}\cap\{\emptyset,\{a\},\{\{a\}\}\{a,\{a\}\}\}=\{\{a\}\}\ne\emptyset. \]
Jan 12

Problem 2. (Due Jan 19.) If \(f:A\to B\) and \(g:B\to C\) are bijections, then so is \(g\circ f:A\to C\).

Extra Credit 1. (Due Jan 19.) Using the notation from the proof of the Schröder-Bernstein Theorem, let \(A=\mathbb{N}\), \(B=\mathbb{Z}\), \(f(n)=n\) and \[g(n)=\begin{cases}1-3n,&n\le0\\3n-1,&n>0\end{cases}.\] Calculate \(h(6)\) and \(h(7)\).

Jan 10

The Schröder-Bernstein theorem was proved.

Jan 8

Problem 1. (Due Jan 17.) Is there a set \(S\) such that \(S\cap\powerset{S}\ne\emptyset\)?

Read §1.1–1.5.

Jan 3

This is the place to look for homework problems, solutions and announcements.