I had hoped to write some more problems and will return to this as soon as I can, but for now here are some (harder) problems to help you think about the course as well as some more recent material. As always, reading Spivak and doing exercises is also useful.
This is just to reinforce today’s lecture. The idea is that many concepts:
Only depend on the behavior of \(f(x)\) in a region \((a-\delta,a+\delta)\) for any \(\delta\).
But is there anything that is not a “local” property of a function?
Here local means some fact that can really be detected in one of these very small neighbourhoods of \(a\). One property is being a maximum (not must a local maximum). Remember that we proved the following:
Theorem: If \(f(x)\) is continuous on a closed interval \([a,b]\), then \(f(x)\) obtains a maximal value. That is, there exists a \(c \in [a,b]\) so that \(f(c) \ge f(x)\) for all \(x \in [a,b]\).
To prove this theorem, we really had to exploit not only continuity but also some extra properties of the real numbers, namely that any non-empty bounded set \(A\) has a least upper bound \(\mathrm{sup}(A)\). One reason why it is hard to prove is that we had to use local properties of continuity to establish something on the entire interval (which by contrast we call a global property). Leaving that aside, the property of being a maximum value is not a local property. That is, suppose you have a differentiable function \(f(x)\) on an interval \([a,b]\), and you know the behavior of the function \(f(x)\) around a point \(c\). On Friday, we will prove the following:
Theorem: If \(f(x)\) is differentiable at \(c\) and \(c\) is a local maximum of \(f(x)\), then \(f'(c)=0\).
However, something we can not do is tell whether \(c\) is actually a maximum of \(f(x)\) on the entire interval just by looking at the behavior around \(x =c\). This is hopefully intuitive, but let’s give an example. Consider the following three functions:
\[\begin{aligned}
a(x) & = 3 x^4 – 20 x^3 + 36 x^2, \\
b(x) & = 12 x^4 – 80 x^3 + 162 x^2 – 108 x + 33, \\
c(x) & = \begin{cases} a(x), & x < 1, \\
b(x), & x \ge 1. \end{cases} \end{aligned}\]
Here is the graph of \(a(x)\) in blue and \(c(x)\) in orange:
I claim that the three functions \(a(x),b(x),c(x)\) are all differentiable. This should be clear for \(a(x)\) and \(b(x)\). For \(c(x)\) it follows from the local principle above except for the point \(x=1\). Note that
\[c(1) = b(1) = 12-80+162-108+33= 19 = 3 – 20 + 36= a(1).\]
To check that \(c(x)\) is differentiable we check that the right and limits both exist and they are both equal. We have
\[\lim_{h \rightarrow 0^{+}} \frac{c(1+h) – c(1)}{h} =
\lim_{h \rightarrow 0^{+}} \frac{b(1+h) – b(1)}{h} = b'(1) = 24.\]
On the other hand, since \(b(1)=a(1)\), we have
\[\lim_{h \rightarrow 0^{-}} \frac{c(1+h) – c(1)}{h} =
\lim_{h \rightarrow 0^{-}} \frac{a(1+h) – a(1)}{h} = a'(1) = 24.\]
The point is that the right and left hand side limits only involve \(a(x)\) or \(b(x)\), and because those functions are differentiable we can compute the limits in terms of those functions and their derivatives. Now let us check the critical points of \(a(x)\), \(b(x)\), and \(c(x)\). We have
\[\begin{aligned} a'(x) & = 12 (-3 + x) (-2 + x) x, \\
b'(x) & = 12 (-3 + x) (-3 + 2 x) (-1 + 2 x) \end{aligned}.\]
Since \(a'(1)=b'(1) = 24\), we get
\[c'(x) = \begin{cases} 12 (-3 + x) (-2 + x) x, & x < 1 \\ 12 (-3 + x) (-3 + 2 x) (-1 + 2 x), & x \ge 1. \end{cases}\] What are the critical points? We get:
We now (finally) get the the point. The functions \(a(x)\) and \(c(x)\) are the same function in a neighbourhood of \(x=0\). So we deduce:
However, the function \(a(x)\) has its mimimum for all \(x\) at \(x=0\), whereas the function \(c(x)\) does not, it’s minimum occurs at \(x=3\). There is no way to tell this just by looking at these functions around \(x=0\).
Here are the solutions by ChatGPT to this week’s midterm. What grade would you give it?
Give your grade in the comments! (Hint: there are definitely some things which are wrong here.)
Problem 1
We need to show that
\[
\lim_{x \rightarrow 1} x^2 = 1
\]
using the \(\varepsilon\)-\(\delta\) definition of a limit.
Solution
To prove that \(\lim_{x \to 1} x^2 = 1\) using the \(\varepsilon\)-\(\delta\) definition, we must show that for any \(\varepsilon > 0\), there exists a \(\delta > 0\) such that if \(0 < |x - 1| < \delta\), then \(|x^2 - 1| < \varepsilon\).
—
Problem 2
We need to construct a set \(A\) with the following properties:
Solution
Consider the set \(A = \{x \in \mathbb{R} : 0 \leq x < 1\}\).
Thus, the set \(A = \{x \in \mathbb{R} : 0 \leq x < 1\}\) satisfies the required conditions.
—
Problem 3
We analyze the conditions to determine whether each implies continuity at \(x = 0\).
Thus, this condition does not ensure continuity.
Therefore, this does not imply continuity at \(x = 0\).
—
Problem 4
Let \(f(x)\) be a continuous function on \(\mathbb{R}\) satisfying \(f(x+1) = f(x)\) for all \(x \in \mathbb{R}\). We need to prove that \(f(x)\) is bounded on \(\mathbb{R}\).
Solution
Therefore, \(f(x)\) is bounded on \(\mathbb{R}\).
I gave ChatGPT the midterm. It scored around 60/100. (Update: I just graded the midterm and was more generous, so 65/100.) It failed miserably on the graphing question, which is maybe expected since it doesn’t have the ability scan in a graph. After some prodding, it produced the following:
which is a somewhat heroic effort in the circumstances.
Let me give ChatGPT’s answers as generated entirely by ChatGPT, making some comments as we go along.
Suppose that \(\alpha\) and \(\beta\) are numbers such that \(\alpha \beta\) and \(\alpha + \beta\) are both integers. Prove that \(\alpha^n + \beta^n\) is an integer for each \(n \in \mathbb{N}\).
Solution:
We are given that \(\alpha \beta\) and \(\alpha + \beta\) are integers. We want to show that \(\alpha^n + \beta^n\) is an integer for each \(n \in \mathbb{N}\).
Let \(s_n = \alpha^n + \beta^n\). We will use a recurrence relation to prove that \(s_n\) is an integer for all \(n \geq 0\).
From the quadratic equation with roots \(\alpha\) and \(\beta\):
\[
x^2 – (\alpha + \beta)x + \alpha \beta = 0,
\]
we have the recurrence relation:
\[
s_{n+2} = (\alpha + \beta) s_{n+1} – \alpha \beta s_n.
\]
\[
s_0 = \alpha^0 + \beta^0 = 2, \quad s_1 = \alpha + \beta.
\]
Both are integers by assumption. By induction, assume \(s_n\) and \(s_{n+1}\) are integers for some \(n \geq 0\). Then, by the recurrence relation:
\[
s_{n+2} = (\alpha + \beta) s_{n+1} – \alpha \beta s_n,
\]
which is an integer because \(\alpha + \beta\), \(\alpha \beta\), \(s_n\), and \(s_{n+1}\) are all integers.
Thus, by the principle of induction, \(s_n = \alpha^n + \beta^n\) is an integer for all \(n \geq 0\).
Frank’s Comments: I would prefer not being so cavalier with writing \(\alpha^0 = 1\) when \(\alpha\) could be zero, but this answer is more or less correct. I would also have preferred that instead of talking about recurrence relations one could just prove that formula directly. That said, with generous grading \(25/25\).
Determine if the following claims are true or false. Justify your answer with a proof.
(a) There exists a function with domain \(\mathbb{R}\) and range the integers.
Solution:
This statement is true. A simple example is the floor function \(\lfloor x \rfloor\), which takes a real number \(x\) and returns the largest integer less than or equal to \(x\). The floor function has domain \(\mathbb{R}\) and range \(\mathbb{Z}\).
(b) The zero function is defined as the function which returns zero for all real numbers — it has domain \(\mathbb{R}\) and range \(0\). Suppose that \(f\) and \(g\) are two functions with domain \(\mathbb{R}\) whose product is equal to the zero function. Then one of \(f\) or \(g\) is the zero function.
Solution:
This statement is false. Consider the functions \(f(x) = x\) and \(g(x) = 0\). Their product is zero for all \(x\), but neither function is identically zero over \(\mathbb{R}\).
Frank’s Comments The function \(g(x)\) is the zero function here! One can easily modify this with \(g(x)=0\) for \(x \ne 0\) and \(g(0) = 1\). With generous grading \(5/10\).
(c) If the domain of \(f\) is all of \(\mathbb{R}\), then the domain of the function \(g(x) = \frac{1}{1 + f(x)^2}\) is also all of \(\mathbb{R}\).
Solution:
This statement is true. Since \(f(x)^2 \geq 0\) for all \(x \in \mathbb{R}\), we have \(1 + f(x)^2 \geq 1\), which means the denominator of \(g(x)\) is never zero. Therefore, the function \(g(x)\) is well-defined for all \(x \in \mathbb{R}\).
Let \(\Gamma(x)\) be a function with domain \((-1, 0) \cup (0, 5]\), such that \(\Gamma(1) = 1\) and \(\Gamma(x+1) = x \Gamma(x)\) for all \(x\) in the domain of \(\Gamma(x)\). Draw the graph of \(\Gamma(x)\), assuming that for \(x \in [1, 5]\), the graph is provided.
Solution:
We can compute the values of \(\Gamma(x)\) for \(x \in [1, 5]\) using the recurrence relation. We know that \(\Gamma(1) = 1\). From the relation \(\Gamma(x+1) = x \Gamma(x)\), we get:
\[
\Gamma(2) = 1 \cdot \Gamma(1) = 1,
\]
\[
\Gamma(3) = 2 \cdot \Gamma(2) = 2,
\]
\[
\Gamma(4) = 3 \cdot \Gamma(3) = 6,
\]
\[
\Gamma(5) = 4 \cdot \Gamma(4) = 24.
\]
Thus, we have the points \(\Gamma(1) = 1\), \(\Gamma(2) = 1\), \(\Gamma(3) = 2\), \(\Gamma(4) = 6\), and \(\Gamma(5) = 24\).
Frank’s Comments: Since ChatGPT couldn’t read the graph, there is not much content here; \(0/20\).
Let \(a_n\) and \(b_n\) be the sequences defined by \(a_0 = b_0 = 1\) and the recurrence relations:
\[
a_{n+1} = 3^{a_n}, \quad b_{n+1} = 2^{b_n}.
\]
Prove the following:
(a) Prove that \(a_n > b_{n+1}\) for \(n \geq 2\).
Solution:
We will use induction to prove that \(a_n > b_{n+1}\) for \(n \geq 2\).
Base case:
For \(n = 2\), we have:
\[
a_2 = 3^{a_1} = 3^1 = 3, \quad b_3 = 2^{b_2} = 2^2 = 4.
\]
Thus, \(a_2 = 3 < b_3 = 4\), which satisfies the inequality.
Inductive step:
Assume \(a_n > b_{n+1}\) for some \(n \geq 2\). We want to show that \(a_{n+1} > b_{n+2}\). We have:
\[
a_{n+1} = 3^{a_n}, \quad b_{n+2} = 2^{b_{n+1}}.
\]
By the inductive hypothesis, \(a_n > b_{n+1}\), so:
\[
a_{n+1} = 3^{a_n} > 3^{b_{n+1}} > 2^{b_{n+1}} = b_{n+2}.
\]
Thus, the inequality holds for \(n+1\), completing the induction.
(b) Prove that \(b_{n+2} > a_n\) for all \(n \geq 0\).
Solution:
We proceed similarly by induction.
Base case:
For \(n = 0\), we have:
\[
b_2 = 2^{b_1} = 2^1 = 2 > a_0 = 1.
\]
Thus, \(b_2 > a_0\) holds.
Inductive step:
Assume \(b_{n+2} > a_n\) for some \(n \geq 0\). We want to show that \(b_{n+3} > a_{n+1}\). We have:
\[
b_{n+3} = 2^{b_{n+2}}, \quad a_{n+1} = 3^{a_n}.
\]
By the inductive hypothesis, \(b_{n+2} > a_n\), so:
\[
b_{n+3} = 2^{b_{n+2}} > 3^{a_n} = a_{n+1}.
\]
Thus, the inequality holds for \(n+1\), completing the induction.
Frank’s Comments: Of course if \(b > a\) then it is not necessarily the case that \(2^b > 3^a\), so the second part is wrong, \(15/25\), for a total of
\[25+25+15=65\]
I’ve talked about how analyzing games naturally leads to inductive arguments, and gave a few examples. Here is a tricky game problem which is a little mind bending. It’s much tricker than anything else I have suggested, so consider it a challenge problem (for fun).
Problem: Alice and Bob are infinitely intelligent, and honest, and they play the following game. They both write down a natural number on a piece of paper (without showing the other) and then give them to Chuck. Let’s call them \(a\) and \(b\). Chuck then reveals to Alice and Bob two numbers; one of the numbers is the sum \(a+b\), and the other is an integer \(c\), but Chuck does not tell either Alice or Bob which is which.
Chuck asks Alice: “do you know Bob’s number”? If Alice says yes, the game ends. Otherwise:
Chuck asks Bob: “do you know Alice’s number?” If Bob says yes, the game ends. Otherwise:
Chuck asks Alice: “do you know Bob’s number”? If Alice says yes, the game ends. Otherwise:
… Chuck keeps going back and forth alternatively asking Bob and Alice the same question. The problem it to show that, after finitely many turns, one of Alice or Bob says yes.
An Example: Suppose that Alice write down \(a = 7\) and Bob writes down \(b = 17\), and that Chuck writes down the numbers \(32\) and \(24\).
It should be very much clear that something inductive is going on in this problem. So the problem is: what is going on?
Although I did this in class, I thought it might be useful to write out a proof here. There are many variations, but it should look something quite similar to this.
Claim: For \(n = 0,1,2,\ldots\) a non-negative integer, the winner of the sticks game is as follows:
Proof: We give a proof by induction starting from \(n = 0\). Let \(P(n)\) mean that the three listed statements above are true for \(n\).
Base Case: Suppose that \(n=0\).
These three statements prove \(P(0)\) is true, which is the base case.
Inductive Step: We shall assume \(P(k)\) and show \(P(k+1)\).
Thus assuming \(P(k)\) we have shown \(P(k+1)\) is true, and so by induction we are done!
Remarks:
Added: A real life application of the sticks game:
Cantor’s argument also allows us to “explicitly” construct irrational numbers. Let’s take a list which includes all the rational numbers between \(0\) and \(1\). First we add \(1\), and then we take \(a/b\) first over the possible denominators \(b > 1\) and then taking all possible numerators \(a\) from \(1\) to \(b-1\). Let’s not even worry about duplicates! So we could take \(r_1, r_2, r_3, \ldots \) to be:
\[1/2,1/3,2/3,1/4,2/4,3/4,1/5,2/5,3/5,4/5,1/6,2/6,3/6,4/6,5/6,1/7, \ldots \]
Taking the opposite convention to class, let’s consider the decimal expansion of these numbers which, if it ends in \(999999\ldots\) we round up. Now we take a real number \(r\) defined as follows:
So here is the list:
\[\begin{aligned}
r_1 & = 0.5000000000 \ldots \\
r_2 & = 0.3333333333 \ldots \\
r_3 & = 0.6666666666 \ldots \\
r_4 & = 0.2500000000 \ldots \\
r_5 & = 0.5000000000 \ldots \\
r_6 & = 0.7500000000 \ldots \\
r_7 & = 0.2000000000 \ldots \\
r_8 & = 0.4000000000 \ldots \\
r_9 & = 0.6000000000 \ldots \\
r_{10} & = 0.8000000000 \ldots \\
\end{aligned}
\]
and so say using the mathematica code
\[ \begin{split}
\texttt{Q := Flatten[Table[a/b, {b, 2, 20}, {a, 1, b – 1}]]} \\
\texttt{Table[If[Mod[Floor[Q[[n]] 10^n], 10] == 1, 1, 2], {n, 1, Length[Q]}]}
\end{split}
\]
We find that
\[r = 0.222222222222222211212222222212222222222222222212222221222222222222222\ldots \]
is an irrational number, because if it were rational in \(0,1\) then it would be equal to \(r_n\) for some \(n\),
but the \(n\)th digit of \(r\) is not equal to the \(n\)th digit of \(r_n\) by construction.
Another fact about decimal expansions of rational numbers is that they are (eventually) repeating. This gives (yet another) way to construct them using decimal expansions.
In class we gave the “classic” proof that \(\sqrt{2}\) is irrational, but we also gave a different proof using analysis. For each pair of positive integers \([a,b]\) with \(a/b \in [0,1]\) with \(b > 1\), we considered the interval
\[ I(a,b):= \left[ \frac{a}{b} – \frac{1}{b^{42}},\frac{a}{b} + \frac{1}{b^{42}} \right]\]
around the point \(a/b\). One possible guess is that the union ofthese intervals entirely covers \((0,1)\) (maybe with some overlap). There certainly will be some overlap since \(I(a,b)\) and \(I(ma,mb)\) are both centered on \(a/b = ma/mb\). But if these intervals do cover the entire interval \([0,1]\) then the total length of all these lines should be at least \(1\). But we can compute the length:
and so on, so the total length is at least
\[ \begin{aligned} S &:=
\frac{2}{2^{42}} + \frac{2}{2^{42}} + \frac{2}{3^{42}}+ \frac{2}{3^{42}}+ \frac{2}{3^{42}} + \frac{2}{4^{42}} + \ldots \\
& = 2 \left(\underbrace{\frac{1}{2^{42}} + \frac{1}{2^{42}}}_{2} + \underbrace{\frac{1}{3^{42}} + \frac{1}{3^{42}} + \frac{1}{3^{42}}}_{3} + \underbrace{\frac{1}{4^{42}} + \ldots + \frac{1}{4^{42}}}_{4} + \ldots \right) \\
& = 2 \left(\frac{2}{2^{42}} + \frac{3}{3^{42}} + \frac{4}{4^{42}}+ \frac{5}{5^{42}}+ \ldots \right) \\
& = 2 \left(\frac{1}{2^{41}} + \frac{1}{3^{41}} + \frac{1}{4^{41}}+ \frac{1}{5^{41}}+ \ldots \right) \\
& = 0.00000000094947\ldots\end{aligned} \]
(We did not and will not justify the last line) which is less than one. So irrational numbers must exist, and lots of them! This proof even shows that if you take a “random” real number \(\alpha\) then unless are really really unlucky, you must have
\[ \left| \alpha – \frac{p}{q} \right| \ge \frac{1}{q^{42}} \]
for all integers \(p\) and \(q\) with \(q > 1\). But unlike the first proof, this proof doesn’t show that any particular number is irrational. It’s a great feat of humanity that \(\pi\) is irrational, but does it also have this property?
Things to think about:
We know (because we have been told) that \(\pi\) is irrational. In fact this was first proven by Lambert in 1760. It is a much harder (and more recent) theorem of Kurt Mahler from the 1950s that
\[ \left| \pi- \frac{p}{q} \right| \ge \frac{1}{q^{42}} \]
for all \(q > 1\). The optimal value of the exponent is not known!
This will be the class blog for 16100 in Autumn 2024, and will be an occasional supplement to the regular course lectures. (I started blogging about courses during the pandemic, but students find the blog useful so have continued to use it.)
Syllabus: can be found here.
