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.
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\).
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.
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*}
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\).
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.
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\).
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.
Problem 14. (Due Feb 16.) Let \(a_1=3\) and \(a_{n+1}=2-1/a_n\) for \(n\in\N\). Analyze the sequence.
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}\).)
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\).
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.
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)\).
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\).
Problem 9. (Due Feb 7.) If \(I\) is an interval, then \(\Q\cap I\ne\emptyset\).
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\).
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\).
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.
Problem 5. (Due Jan 29.) Prove Theorem 2.11(d) from the notes.
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.
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\).
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. \]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)\).
The Schröder-Bernstein theorem was proved.
Problem 1. (Due Jan 17.) Is there a set \(S\) such that \(S\cap\powerset{S}\ne\emptyset\)?
Read §1.1–1.5.
This is the place to look for homework problems, solutions and announcements.