Tag: math

Some Integration Drills

Problem 1. Evaluate the integral $\displaystyle \int(x^2 + \tan x - 3)\, \mathrm dx$ .

(Click for Solution)

Solution. By the linearity of integration,

$\displaystyle \begin{aligned}\int(x^2 + \tan x - 3)\, \mathrm dx &= \int x^2\, \mathrm dx + \int \tan x \, \mathrm dx - \int 3\, \mathrm dx \\ &= \frac 13 x^3 - \ln|{\cos x}| - 3x + C.\end{aligned}$

Problem 2. Evaluate the integral $\displaystyle \int \left(\frac{1}{9 + x^2} + \frac{1}{\sqrt{4-x^2}} \right)\, \mathrm dx$ .

(Click for Solution)

Solution. By the linearity of integration,

$\displaystyle \begin{aligned} \int \left(\frac{1}{9 + x^2} + \frac{1}{\sqrt{4-x^2}} \right)\, \mathrm dx &= \int \frac{1}{9 + x^2} \, \mathrm dx + \int \frac{1}{ \sqrt{4-x^2} } \, \mathrm dx \\ &= \int \frac{1}{3^2 + x^2} \, \mathrm dx + \int \frac{1}{ \sqrt{2^2-x^2} } \, \mathrm dx \\ &= \frac 13 \tan^{-1} \left( \frac x3 \right) + \sin^{-1} \left( \frac x2 \right) + C. \end{aligned}$

Problem 3. Evaluate the integral $\displaystyle \int_0^1 x \sec(x^2) \tan(x^2)\, \mathrm dx$ .

(Click for Solution)

Solution. By the substitution $\displaystyle u = x^2 \Rightarrow \mathrm dx = \frac 1{2x}\, \mathrm du$ ,

$\displaystyle \begin{aligned} \int x \sec(x^2) \tan(x^2)\, \mathrm dx &= \int x \sec(u) \tan(u) \cdot \frac{1}{2x}\, \mathrm du \\ &= \frac 12 \int \sec(u) \tan(u)\, \mathrm du \\ &= \frac 12 \sec(u) + C \\ &= \frac 12 \sec(x^2) + C. \end{aligned}$

Hence, substituting the limits,

$\displaystyle \begin{aligned} \int_0^1 x \sec(x^2) \tan(x^2)\, \mathrm dx &= \frac 12 [\sec(x^2)]_0^1\\ &= \frac 12 (\sec(1) - \sec(0)) \\ &= \frac 1{2 \cos(1)} - \frac 12 \\ &\approx 0.425, \end{aligned}$

when approximated to 3 decimal places.

Problem 4. Evaluate the integral $\displaystyle \int \tan^3 x\, \mathrm dx$ .

(Click for Solution)

Solution. Using the Pythagorean identity $\sec^2 x = \tan^2 x +1$ ,

$\displaystyle \begin{aligned} \int \tan^3 x\, \mathrm dx &= \int \tan x \tan^2 x\, \mathrm dx \\ &= \int \tan x (\sec^2 x - 1)\, \mathrm dx \\ &= \int \tan x \sec^2 x \, \mathrm dx - \int \tan x\, \mathrm dx \\ &= \int \tan x \sec^2 x \, \mathrm dx -(- \ln|{\cos x}|) + C.\end{aligned}$

For the first integral, make the substitution $\displaystyle u = \tan x \Rightarrow \mathrm dx = \frac{1}{\sec^2 x}\, \mathrm du$ . Then

$\displaystyle \begin{aligned}\int \tan x \sec^2 x \, \mathrm dx &= \int u \sec^2 x \cdot \frac{1}{\sec^2 x}\, \mathrm du \\ &= \int u\, \mathrm du \\ &= \frac 12 u^2 + C\\ &= \frac 12 \tan^2 x + C.\end{aligned}$

Therefore, $\displaystyle \int \tan^3 x\, \mathrm dx = \frac 12 \tan^2 x + \ln|{\cos x}| + C.$

Problem 5. Evaluate the integral $\displaystyle \int \sin(\ln \theta)\, \mathrm d\theta$ .

(Click for Solution)

Solution. Make the substitution $u = \ln \theta \Rightarrow \mathrm d\theta = e^u\, \mathrm du$ . Then

$\displaystyle \int \sin(\ln \theta)\, \mathrm d\theta = \int e^u \sin(u)\, \mathrm du.$

Integrating by parts twice,

$\displaystyle \begin{aligned}\int e^u \sin(u)\, \mathrm du &= \underbrace{e^u}_{\mathrm I}\, \underbrace{\sin(u)}_{\mathrm S} - \int \underbrace{e^u}_{\mathrm I}\, \underbrace{\cos(u)}_{\mathrm D}\, \mathrm du \\ &= e^u \sin(u) - \int e^u \cos(u)\, \mathrm du\\ &= e^u \sin(u) - \left(\underbrace{e^u}_{\mathrm I}\, \underbrace{\cos(u)}_{\mathrm S} - \int \underbrace{e^u}_{\mathrm I}\, \underbrace{-\sin(u)}_{\mathrm D}\, \mathrm du\right) \\ &= e^u \sin(u) - \left(e^u \cos(u) + \int e^u \sin(u) \, \mathrm du\right) \\ &= e^u \sin(u) - e^u \cos(u) - \int e^u \sin(u)\, \mathrm du \\&= e^u (\sin(u) - \cos(u)) - \int e^u \sin(u)\, \mathrm du.\end{aligned}$

By algebruh,

$\displaystyle \begin{aligned} \int e^u \sin(u)\, \mathrm du + \int e^u \sin(u)\, \mathrm du &= e^u (\sin(u) - \cos(u)) \\ 2 \int e^u \sin(u)\, \mathrm du &= e^u (\sin(u) - \cos(u)) \\ \int e^u \sin(u)\, \mathrm du &= \frac 12 e^u (\sin(u) - \cos(u)) + C\\ \int \sin(\ln \theta)\, \mathrm d\theta &= \frac 12 \theta (\sin(\ln \theta) - \cos(\ln \theta)) + C.\end{aligned}$

Problem 6. Evaluate the integral $\displaystyle \int \left(\frac{1}{36 - x^2} + \frac{1}{\sqrt{36-x^2}} \right)\, \mathrm dx$ .

(Click for Solution)

Solution. By the linearity of integration,

$\displaystyle \begin{aligned} \int \left(\frac{1}{36 - x^2} + \frac{1}{\sqrt{36 -x^2}} \right)\, \mathrm dx &= \int \frac{1}{36 - x^2} \, \mathrm dx + \int \frac{1}{ \sqrt{36-x^2} } \, \mathrm dx \\ &= \int \frac{1}{6^2 - x^2} \, \mathrm dx + \int \frac{1}{ \sqrt{6^2-x^2} } \, \mathrm dx \\ &= \frac 1{2 \cdot 6} \ln \left| \frac{6+x}{6-x} \right| + \sin^{-1} \left( \frac x6 \right) + C\\ &= \frac 1{12} \ln \left| \frac{6+x}{6-x} \right| + \sin^{-1} \left( \frac x6 \right) + C. \end{aligned}$

Problem 7. Evaluate the integral $\displaystyle \int_0^2 x \sin(x^2 + 5)\, \mathrm dx$ .

(Click for Solution)

Solution. Making the substitution $u = x^2 + 5$ yields

$\displaystyle \mathrm du = 2x\, \mathrm dx,\quad u(0) = 5, \quad u(2) = 9.$

Therefore,

$\displaystyle \begin{aligned} \int_0^2 x \sin(x^2 + 5)\, \mathrm dx &= \frac 12 \int_0^2 \sin(x^2 + 5) \cdot 2x\, \mathrm dx \\ &= \frac 1{2}\int_5^9 \sin(u)\, \mathrm du \\ &= \frac 12 [-\cos(u)]_5^9 \\ &= \frac 12 (-\cos(9) - (-\cos(5))) \\ &= \frac 12 (\cos(5) - \cos(9)) \approx 0.597, \end{aligned}$

when approximated to 3 decimal places.

Problem 8. Evaluate the integral $\displaystyle \int \cot^3 x\, \mathrm dx$ .

(Click for Solution)

Solution. Recall that $\cot(x) = \tan(\pi/2 - x)$ . Making the substitution $u = \pi/2-x \Rightarrow \mathrm du = -\mathrm dx$ then using the result in Problem 4,

$\displaystyle \begin{aligned} \int \cot^3 x\, \mathrm dx &= \int \tan^3 (\pi/2-x)\, \mathrm dx \\ &= \int \tan^3(u) \cdot -1\, \mathrm du \\ &= -\int \tan^3(u)\, \mathrm du \\ &= -\left( \frac 12 \tan^2 u + \ln|{\cos u}| \right) + C \\ &= -\left( \frac 12 \tan^2 (\pi/2-x) + \ln|{\cos (\pi/2-x)}| \right) + C \\ &= -\left( \frac 12 \cot^2 x + \ln|{\sin x}| \right) + C \\ &= - \frac 12 \cot^2 x - \ln|{\sin x}| + C \end{aligned}$

Problem 9. Evaluate the integral $\displaystyle \int e^{2\theta} \sin (e^\theta) \, \mathrm d\theta$ .

(Click for Solution)

Solution. Making the substitution $\displaystyle u = e^{\theta} \Rightarrow \mathrm d\theta = \frac 1{u}\, \mathrm du$ then integrating by parts,

$\displaystyle \begin{aligned} \int e^{2\theta} \sin(e^\theta) \, \mathrm d\theta &= \int u^2 \sin(u)\cdot \frac 1{u}\, \mathrm du \\ &= \int u \sin(u)\, \mathrm du\\ &= \underbrace{-\cos(u)}_{\mathrm I} \underbrace{u}_{\mathrm S} - \int \underbrace{-\cos(u)}_{\mathrm I}\underbrace{1}_{\mathrm D}\, \mathrm du \\ &= -u \cos u + \int \cos u\, \mathrm du\\ &= -u \cos u + \sin u + C\\ &= -e^\theta \cos(e^\theta) + \sin(e^\theta) + C. \end{aligned}$

Problem 10. Given that

$f(x) = \begin{cases} 1 - |x|, & |x| \leq 1, \\ 0, &\text{otherwise},\end{cases}$

evaluate $\displaystyle \int_0^{2} f(x^2-1)\, \mathrm dx$ .

(Click for Solution)

Solution. By the definition of $f$ ,

$f(x^2 - 1) = \begin{cases} 1 - |x^2 - 1|, & |x^2 - 1| \leq 1, \\ 0, &\text{otherwise}.\end{cases}$

Parsing the inequality $|x^2 - 1| \leq 1 \iff |x| \leq \sqrt 2$ ,

$f(x^2 - 1) = \begin{cases} 1 - |x^2 - 1|, & |x| \leq \sqrt 2, \\ 0, &\text{otherwise}.\end{cases}$

By definition of the absolute value,

$|x^2 - 1| = \begin{cases} x^2 - 1, & |x| \geq 1, \\ 1 - x^2, &|x| \leq 1.\end{cases}$

Parsing the inequalities again,

$f(x^2 - 1) = \begin{cases} x^2, & 0 \leq |x| \leq 1, \\ 2-x^2 , & 1 \leq |x| \leq \sqrt 2, \\ 0, &\text{otherwise}.\end{cases}$

Therefore, we can evaluate the integral as

$\begin{aligned} \displaystyle \int_0^{2} f(x^2-1)\, \mathrm dx &= \int_0^1 f(x^2 - 1)\, \mathrm dx + \int_1^{\sqrt 2} f(x^2 - 1)\, \mathrm dx + \int_{\sqrt 2}^{2} 0\, \mathrm dx \\ &= \int_0^1 x^2\, \mathrm dx + \int_1^{\sqrt 2} (2 - x^2)\, \mathrm dx+ 0 \\ &= \left[ \frac{x^3}{3}\right]_0^1 + \left[ 2x - \frac{x^3}{3} \right]_1^{\sqrt 2} \\ &= \left( \frac 13 - 0 \right) + \left( 2\sqrt 2 - \frac{2\sqrt 2}{3} \right) \\ &= \frac 13 + \frac{4}{3}\sqrt 2. \end{aligned}$

—Joel Kindiak, 20 Jan 25, 0925H

January 20, 2025

ai, Calculus, math, mathematics, physics
Mashed Potato Rationals

Definition 1. For sets $K, L \subseteq \mathbb R$ , we say that $K$ is dense in $L$ if for any $x,y \in L$ with $x < y$ , there exists $z \in K$ such that $x < z < y$ . For this definition, we do not assume $K \subseteq L$ .

Problem 1 (Density Theorem). Prove that $\mathbb Q$ is dense in $\mathbb R$ .

(Click for Solution)

Solution. Fix $x,y \in \mathbb R$ such that $x < y$ . Then $y-x > 0$ . By the Archimedean property, find $n \in \mathbb N$ such that

$\displaystyle 0 < \frac 1n < y-x \quad \Rightarrow \quad nx < nx + 1 < ny.$

Intuitively, there should be one integer between $nx$ and $nx + 1$ . To formulate this rigorously, the definition of the floor function $\lfloor \cdot \rfloor : \mathbb R \to \mathbb Z$ yields the estimate

$\lfloor nx \rfloor \leq nx < \lfloor nx \rfloor + 1.$

Hence,

$\displaystyle nx < \lfloor nx \rfloor +1 \leq nx + 1 < ny \quad \Rightarrow \quad x < \frac{\lfloor nx \rfloor+1}{n} < y.$

Set $z := (\lfloor nx \rfloor+1)/n \in \mathbb Q$ to obtain the desired result.

Problem 2. Prove that $\mathbb Q(\sqrt 2) := \{r\sqrt 2 : r \in \mathbb Q\}$ is dense in $\mathbb R$ .

(Click for Solution)

Solution. Fix $x,y \in \mathbb R$ such that $x < y$ . Dividing by $\sqrt 2$ yields $x/\sqrt 2 < y/\sqrt 2$ . By Problem 1, find a nonzero rational number $r$ such that

$\displaystyle \frac x{\sqrt 2} < r < \frac y{\sqrt 2}\quad \Rightarrow \quad x < r\sqrt 2 < y.$

Define $z := r\sqrt 2 \in \mathbb R \backslash \mathbb Q$ , as required.

Problem 3. Suppose $K \subseteq L$ and $K$ is dense in $M$ . Then $L$ is dense in $M$ .

(Click for Solution)

Solution. Fix $x,y \in M$ such that $x < y$ . Since $K$ is dense in $M$ , there exists $z \in K \subseteq L$ such that $x < z < y$ , as required.

Problem 4. Deduce that $\mathbb R \backslash \mathbb Q$ is dense in $\mathbb R$ .

(Click for Solution)

Solution. We claim that $\mathbb Q(\sqrt 2) \subseteq \mathbb R \backslash \mathbb Q$ , since $\sqrt{2} = (r\sqrt 2)/r$ (so that $r \sqrt 2 \in \mathbb Q \Rightarrow \sqrt 2 \in \mathbb Q$ , a contradiction).

By Problems 2 and 3, $\mathbb R \backslash \mathbb Q$ is dense in $\mathbb R$ .

Problem 5. Suppose $K$ is dense in $L$ and $L$ is dense in $M$ . Then $K$ is dense in $M$ .

(Click for Solution)

Solution. Fix $x,y \in M$ such that $x < y$ . Since $L$ is dense in $M$ , there exists $u \in L \subseteq M$ such that $x < u < y$ . Apply the density of $L$ in $M$ again to obtain $v \in L$ such that $u < v < y$ .

Since $K$ is dense in $L$ , there exists $z \in K$ such that $u < z < v$ . Therefore,

$x < u < z < v < y \quad \Rightarrow \quad x < z < y,$

as required.

Problem 6. Prove that for continuous functions $f, g : \mathbb R \to \mathbb R$ and $K$ dense in $L$ , if $f|_{K} = g|_{K}$ , then $f|_L = g|_L$ .

(Click for Solution)

Solution. Fix $x \in L$ . For each $n \in \mathbb N$ , since $K$ is dense in $L$ , find $x_n \in K$ such that $|x_n - x| < 1/n$ . Taking $n \to \infty$ , since $| \cdot |$ is continuous,

$\displaystyle \left| \lim_{n \to \infty} x_n - x \right| = \lim_{n \to \infty} |x_n - x| \leq \lim_{n \to \infty} \frac 1n = 0.$

Therefore, $x_n \to x$ , so that by the continuity of $f, g$ ,

$\displaystyle f(x) = \lim_{n \to \infty} f(x_n) = \lim_{n \to \infty} g(x_n) = g(x).$

Since $x \in L$ is arbitrary, $f|_L = g|_L$ .

Corollary 1. By Problem 1, $\mathbb Q$ is dense in $\mathbb R$ . Hence, by Problem 6, for any $a > 0$ , the continuous exponential $\exp_a$ with base $a > 0$ , defined by $\exp_a(x) := a^x$ , is unique.

—Joel Kindiak, 19 Jan 25, 1633H

January 19, 2025

geometry, math, mathematics, number-theory, Probability
The Foundation of Real Analysis
You may think that constructing the real numbers is the foundation of real analysis. Theoretically, that is true. How can you analyse the real numbers if there aren’t real numbers to begin with?

The practical foundation of real analysis, however, is more properly seen as the notion of limits. Why is that so? The Cauchy construction of real numbers boils down to creating the real numbers using the limits (or lack thereof) of sequences of rational numbers, so we could have started here if we wanted to.

So let’s start by talking about sequences, then limits. For limits, we will need to measure the notion of “closeness”, and that will require us to define the absolute value function. For real analysis, we will adopt the convention $\mathbb N = \mathbb N^+$ so that $0 \notin \mathbb N$ .

Definition 1. Let $K$ be a set. A $K$ -sequence is a function $x : \mathbb N \to K$ . Commonly, we denote $x_n \equiv x(n)$ for each $n$ , and $x \equiv \{x_n\}$ . A real-valued sequence is an $\mathbb R$ -sequence.

When $\mathbb K$ is a field, we inherit many properties of functions into a field.

Theorem 1. Let $\mathbb K$ be a field. For $\mathbb K$ -sequences $x,y$ and any number $k \in \mathbb K$ , $x + y$ , $kx$ are $\mathbb K$ -sequences. In particular, $x-y := x+(-y)$ is a $\mathbb K$ -sequence.

We can also define division of sequences, but care needs to be taken to handle zeroes. We will define the reciprocal sequence in one way for simplicity.

Theorem 2. Let $x$ be a $\mathbb K$ -sequence. Suppose there exists $N \in \mathbb N$ such that for $n > N$ , $x_n \neq 0$ . Then we can define the sequence $y : \mathbb N \to \mathbb K$ by

$y_n := \begin{cases} 0 &\quad \text{if}\ n \leq N, \\ 1/x_n & \quad \text{if}\ n > N,\end{cases}$

such that for $n > N$ , $x_ny_n = 1$ .

We also want to talk about limits. Roughly speaking, we want to write $x_n \to L$ to mean $x_n \approx L$ when $n$ is large. To define $\approx$ in this context requires a notion of closeness (of which one of its most general forms is described using topology; but not in this discussion).

To do that, our tool of choice will be the absolute value function. For the rest of this post, we will let $\mathbb K$ be an ordered field.

Lemma 1. For any $x \in \mathbb K$ , $x^2 \geq 0$ . Furthermore, if $x \neq 0$ , then $x^2 > 0$ . In particular, $1 > 0$ .

Proof. By the antisymmetry of $\leq$ , $x\geq 0$ or $x \leq 0$ . In the former case,

$x^2 = x \cdot x \geq 0 \cdot 0 = 0.$

In the latter case, $x \leq 0$ implies $-x \geq 0$ so that

$x^2 = (-x)^2 \geq 0.$

Finally, if $x \neq 0$ , then

$\displaystyle x^2 = 0\quad \Rightarrow \quad x = \frac 1x \cdot x^2 = \frac 1x \cdot 0 = 0,$

a contradiction. Thus, $x \neq 0 \Rightarrow x^2 \neq 0$ . Combined with $x^2 \geq 0$ , we have $x^2 > 0$ . For the final result, $1 = 1\cdot 1 = 1^2 > 0$ .

Definition 2. The absolute value function $\mathbb | \cdot | : \mathbb K \to \mathbb K_{\geq 0}$ is the function defined by

$|x| := \begin{cases}x &\quad \text{if}\ x \geq 0, \\ -x &\quad \text{if}\ x < 0.\end{cases}$

There are many intriguing properties involving the absolute value function, which we list in the theorem below.

Theorem 3. The absolute value function satisfies the following properties:
- For any $x \in \mathbb K$ , $|x| \geq 0$ .
- For any $x \in \mathbb K$ , $|x| = 0\Rightarrow x = 0$ .
- For any $x,y \in \mathbb K$ , $|xy| = |x||y|$ .
- (Triangle Inequality) For any $x,y \in \mathbb K$ , $|x+y| \leq |x| + |y|$ .
Proof. For the first property, $x \geq 0 \Rightarrow |x| = x \geq 0$ and

$x \leq 0 \quad \Rightarrow \quad |x| = -x \geq -0 = 0.$

For the second property, $x^2 = |x|^2 = 0^2 = 0 \Rightarrow x = 0$ .

The third property is an exercise in case-splitting (there are four cases to compute), which we omit. For the fourth property, we first observe that for any $x,y \in \mathbb K$ ,

$-|x| \leq x \leq |x|,\quad -|y| \leq y \leq |y|.$

Adding the inequalities,

$-(|x| + |y|) \leq x + y \leq |x| + |y|\quad \Rightarrow \quad |x+y| \leq |x| + |y|$

by case-splitting.

Corollary 1. We have as a consequence the following useful properties of the absolute value function:
- For any $x \in \mathbb K$ , $|{-x}| = |x|$ .
- For any $x,y \in \mathbb K$ , $x=y$ if and only if for any $\epsilon \in \mathbb K^+$ , $|x-y| < \epsilon$ .
Proof. The first property follows from

$|{-x}| = |(-1)\cdot x| = |{-1}||x| = -(-1) \cdot |x| = 1 \cdot |x| = |x|.$

For the second property, first assume $y = 0$ . The direction $(\Rightarrow)$ is immediate. For the direction $(\Leftarrow)$ , suppose for any $\epsilon > 0$ that

$|x| < \epsilon \quad \Rightarrow \quad |x| \leq \epsilon = 0 + \epsilon.$

This implies $|x| \leq 0$ . By definition of $|\cdot |$ , $|x| \geq 0$ . Hence,

$0 \leq |x| \leq 0 \quad \Rightarrow \quad |x| = 0 \quad \Rightarrow \quad x = 0.$

For the general case,

$x = y \quad \iff \quad x-y = 0 \quad \iff \quad \forall \epsilon > 0\quad |x-y| < \epsilon.$

With a sufficiently robust idea of the absolute value function, we are now ready to define the limit of a sequence, if it exists.

Definition 3. Let $\{x_n\}$ be a $\mathbb K$ -sequence. For any $L \in \mathbb K$ , we write $x_n \to L$ to mean that

$\forall \epsilon \in \mathbb K^+ \quad \exists N \in \mathbb N:\quad n>N\quad \Rightarrow \quad |x_n - L| <\epsilon.$

We say that $\{x_n\}$ converges in $K \subseteq \mathbb K$ if there exists $L \in K$ such that $x_n \to L$ .

Actually, a very useful perspective to adopt is to view sequences with limits in terms of sequences with limit $0$ .

Theorem 4. Let $x_n$ be a $\mathbb K$ -sequence. Then $x_n \to 0 \iff |x_n| \to 0$ . More generally, $x_n \to L\iff |x_n - L| \to 0$ .

Proof. Use the observation that $|x| \geq 0$ implies $||x|| = |x|$ .

Let’s do arithmetic with sequences, but start with limit $0$ for simplicity (we’ll perform some tricks later on to handle general limits).

Now for sequences with other kinds of limits, how do we know they are unique? For $\mathbb K$ -sequences it turns out that limits must be unique.

Lemma 2. For $k \in \mathbb K$ , define the constant sequence $\{k_n\} \equiv \{k\}$ by $k_n : \mathbb N \to \mathbb K$ , $k_n =k$ . Then $k_n \to 0$ implies $k = 0$ .

Proof. Fix $\epsilon > 0$ . Since $k_n \to 0$ , there exists $N \in \mathbb N$ such that $n > N$ implies

$|k| = |k-0| = |k_n-0| < \epsilon.$

This implies $k = 0$ , as required.

Lemma 3. Let $\{x_n\}$ , $\{y_n\}$ be $\mathbb K$ -sequences such that $x_n \to 0$ and $y_n \to 0$ and $k \in \mathbb K$ . Then

$x_n + y_n \to 0,\quad k x_n \to 0,\quad x_n - y_n \to 0,\quad x_n y_n \to 0.$

Proof. Fix $\epsilon > 0$ . Since $x_n \to 0$ , for any $k_1 > 0$ , there exists $N_1(k_1) \in \mathbb N$ such that

$n > N_1(k_1) \quad \Rightarrow \quad |x_n| < k_1 \epsilon.$

Since $y_n \to 0$ , for any $k_2 > 0$ , there exists $N_2(k_2) \in \mathbb N$ such that

$n > N_2(k_2) \quad \Rightarrow \quad |y_n| < k_2 \epsilon.$

To prove all of these limit laws, the key is to particularise $k_1 >0,k_2 >0$ so that the result is bounded by $\epsilon$ . For the first identity, use the triangle inequality so that for $n > N_1(k_1) + N_2(k_2)$ ,

$|x_n + y_n| \leq |x_n| + |y_n| < k_1 \epsilon + k_2\epsilon = (k_1 + k_2)\epsilon.$

Thus, stipulating $k_1=k_2=1/2$ does the trick. Then there will be corresponding $n > N_1(1/2) + N_2(1/2)$ such that

$|x_n + y_n| < (k_1+k_2)\epsilon = (1/2 + 1/2)\epsilon = \epsilon.$

For the second identity, the result is obvious if $k = 0$ . If $k \neq 0$ , then $|k| > 0$ so that setting $k_1 = 1/|k| >0$ yields

$\displaystyle n > N_1 \quad \Rightarrow \quad|k x_n| = |k||x_n| < |k| \cdot \frac{1}{|k|} \cdot \epsilon = \epsilon.$

For the third identity,

$x_n - y_n = x_n + (-1) \cdot y_n \to 0 + (-1) \cdot 0 = 0.$

For the fourth identity, we aren’t assuming that $\mathbb K = \mathbb R$ , and so will avoid the use of $\sqrt{\cdot}$ , which may or may not be well-defined. Instead, we set $k_1 =1/\epsilon, k_2 = 1$ so that for $n > N_1(1/\epsilon)+ N_2(1)$ ,

$|x_n y_n| = |x_n| |y_n| < ( k_1 \epsilon ) \cdot ( k_2 \epsilon ) = 1 \cdot \epsilon = \epsilon .$

The squeeze theorem is a ridiculously useful limit property.

Lemma 4. Let $\{x_n\}$ , $\{y_n\}$ , $\{z_n\}$ be $\mathbb K$ -sequences such that $x_n \to 0$ and $y_n \to 0$ . Suppose there exists $N \in \mathbb N$ such that

$n > N \quad \Rightarrow \quad x_n \leq z_n \leq y_n.$

Then $z_n \to 0$ .

Proof. Fix $\epsilon > 0$ . Since $x_n \to 0$ , for any $k_1 > 0$ , there exists $N_1(k_1) \in \mathbb N$ such that

$n > N_1(k_1) \quad \Rightarrow \quad |x_n| < k_1 \epsilon \quad \Rightarrow \quad x_n \geq -|x_n| > -k_1 \epsilon.$

Since $y_n \to 0$ , for any $k_2 > 0$ , there exists $N_2(k_2) \in \mathbb N$ such that

$n > N_2(k_2) \quad \Rightarrow \quad |y_n| < k_2 \epsilon \quad \Rightarrow \quad y_n \leq |y_n| < k_2 \epsilon.$

Setting $k_1 = k_2 = 1$ , for $n > N + N_1(1) + N_2(1)$ ,

$-\epsilon < x_n \leq z_n \leq y_n < \epsilon \quad \Rightarrow \quad -\epsilon < z_n < \epsilon\quad \Rightarrow \quad |z_n| < \epsilon.$

Therefore, $z_n \to 0$ , as required.

Now we want to talk about general limits. Let’s first show that limits in ordered fields must be unique.

Theorem 5. Let $\{x_n\}$ be a $\mathbb K$ -sequence. Suppose $x_n \to L_1$ and $x_n \to L_2$ . Then $L_1 = L_2$ . This allows us to write

$\displaystyle x_n \to L \quad \iff \quad \lim_{n \to \infty}x_n = L$

without ambiguity, whenever such an $L$ exists.

Proof. Observe that $L_1 - x_n = (-1) \cdot (x_n - L) \to 0$ and $x_n - L_2 \to 0$ so that

$L_1 - L_2 = (L_1 - x_n) + (x_n - L_2) \to 0.$

Since $L_1,L_2$ are constants, $L_1 - L_2 = 0$ so that $L_1 = L_2$ .

This brings us to the star of any analysis on limits: the limit laws.

Theorem 6 (Limit Laws). Let $\{x_n\},\{y_n\},\{z_n\}$ be $\mathbb K$ -sequences. Suppose $x_n \to x$ , $y_n \to y$ , and $k \in \mathbb K$ . Then

$x_n \pm y_n \to x \pm y,\quad kx_n \to kx,\quad x_ny_n \to xy.$

Furthermore, if there exists $N \in \mathbb N$ such that

$n > N \quad \Rightarrow \quad x_n \geq 0,$

then $x \geq 0$ . Finally, if $x = y = z$ and there exists $N \in \mathbb N$ such that

$n > N \quad \Rightarrow \quad x_n \leq z_n \leq y_n,$

then $z_n \to z$ .

Proof. The first set of limit laws can be proven algebraically:

$\begin{aligned} (x_n \pm y_n) - (x \pm y) &= (x_n - x) \pm (y_n - y) \to 0 \pm 0 = 0, \\ kx_n - kx &= k (x_n - x) = k \cdot 0 = 0, \\ x_n y_n - xy &= (x_n - x + x) \cdot (y_n - y + y) - xy \\ &= (x_n - x)(y_n - y) + y (x_n - x) + x(y_n - y)\\ &\to 0 + 0 + 0 = 0,\end{aligned}$

as required. The squeeze theorem also works since we can apply the zero-limit case to

$x_n - z \leq z_n - z \leq y_n - z$

so that $x_n - z \to 0, y_n - z \to 0$ implies $z_n - z \to 0$ .

For the monotonicity property, fix $\epsilon > 0$ . Since $x_n \to x$ , find $N_1 \in \mathbb N$ so that for $n > N_1$ ,

$|x_n - x| < \epsilon \quad \Rightarrow \quad x_n < x+\epsilon.$

For $n > N + N_1$ , $0 \leq x_n < x+\epsilon$ . Since $\epsilon$ is arbitrary, $0 \leq x$ , as required.

There is one more question worth asking: if $x_n \to x$ , does it always hold that $1/x_n \to 1/x$ ? Well, if $x = 0$ , then we’ll run into problems, and if $x \neq 0$ , this result is plausibly true. You’ll be pleased to know that this result is true. However, this exploration is worth its own exercise since we won’t be needing it as much in our real-analytic discussion.

—Joel Kindiak, 19 Dec 24, 1508H
January 15, 2025

groups, math, mathematics, number-theory, Topology
The Logic of Logic
If pure mathematics is a language, then numbers and variables constitute letters, definitions constitute words, and theorems constitute short paragraphs, all building up to a unified story that explains the explanation for the world. What is its grammar? Logic.

Definition 1. A proposition is a sentence that is either true, denoted $\mathrm T$ , or not, denoted $\neg \mathrm T$ , but not both. A true proposition $\mathrm T$ is called a theorem. We will always make the following notations:

$\mathrm T =\mathrm T,\quad \neg \mathrm T = \neg \mathrm T,\quad \mathrm T \neq \neg \mathrm T,\quad \neg \mathrm T\neq \mathrm T.$

This is technically known as the law of excluded middle, which agrees with our intuition of truth. We will use this starting point for further discussion.

It helps us at times to make the abbreviation $\mathrm F := \neg \mathrm T$ , called false. These are called truth values. This gives us the following definition for the negation.

Definition 2. The negation $\neg$ is defined as follows:

$\neg \mathrm T = \mathrm F,\quad \neg \mathrm F := \mathrm T.$

To condense our definitions, we can use a truth table:

This gives us the following observation by repeated uses of said notation:

$\neg(\neg \mathrm T) = \mathrm T,\quad \neg(\neg \mathrm F) = \mathrm F$ .

More generally, we can discuss logic from an algebraic lens.

Definition 3. A propositional variable $p$ is a placeholder that takes on exactly one of the truth values $\mathrm T$ or $\mathrm F$ .

We want to discuss the truth values of two propositional variables $p, q$ . To do that, we need to define the biconditional.

Definition 4. Define the biconditional $\leftrightarrow$ using the following truth table:

For any propositional variable $p$ and any proposition variable $q$ defined in terms of $p$ , we write $p = q$ if $(p \leftrightarrow q)$ is a theorem for any substitution of $p$ .

Theorem 1. Let $p$ be a propositional variable. Then $\neg(\neg p) = p$ .

Proof. We use the following truth table argument:

Many a time, we want to treat theorems as propositional variables. Propositions formed using existing propositions are known as compound statements. We can formalise this using tautologies, with their negations being contradictions.

Definition 5. A compound statement $t$ is a tautology if $t$ is a theorem regardless of substitution of truth values.

With this vocabulary, for any compound statement $p$ and any compound statement $q$ defined in terms of $p$ , we write $p = q$ to mean that $(p \leftrightarrow q) = t$ .

A corollary is a theorem that, for readability purposes, is a straightforward consequence of a previously established theorem.

Corollary 1. For any propositional variable $p$ , $(\neg(\neg p) \leftrightarrow p) = t$ .

A compound statement $c$ is a contradiction if $c = \neg t$ for some tautology $t$ .

Corollary 2. Let $t$ be a tautology and $c$ be a contradiction. Then $c$ is always false, and $\neg c = t$ .

Based on the starting points $\mathrm T$ and $\mathrm F = \neg \mathrm T$ , we can define many logical connectors. One crucial one is known as the conjunction.

Definition 6. Define the conjunction $\wedge$ using the following truth table:

The conjunction has many useful properties. But first, we need to establish some results pertaining tautologies and contradictions. These will be lemmas—theorems that, for readability sake, are intermediate steps to prove more significant theorems.

Lemma 1. Let $p$ be any propositional variable. Then

$p \wedge t = p = t \wedge p, \quad p \wedge c = c = c \wedge p.$

Proof. Use a truth table argument.

We want to eventually prove propositions such as $p \wedge q = q \wedge p$ . However, we first need to prove that we can chain equalities, i.e. that $p=q$ and $q=r$ implies $p=r$ .

Definition 7. Define the implication $\to$ using the following truth table:

To prove our famous results, we need lemmas, which are theorems that, for readability purposes again, are intermediate steps required to prove a theorem.

Lemma 2. For any propositional variable $p$ ,

$(t \to p) = p,\quad (p \to p) = t,\quad (c \to p) = t.$

Proof. Use a truth table argument.

Our next lemma requires us to chain equalities of propositional variables. This helps us prove the commutativity of conjunction.

Lemma 3. For propositional variables $p, q, r$ ,

$(((p=q) \wedge (q=r)) \to (p=r)) = t.$

Proof. We remark that for any substitution of truth values into $p,q,r$ , if $((p=q) \wedge (q=r)) = \mathrm F$ , then

$(((p=q) \wedge (q=r)) \to (p=r)) = \mathrm T$

automatically. Thus, we will suppose that $((p=q) \wedge (q=r)) = \mathrm T$ . By definition of the truth value of the conjunction, we have $p = q$ and $q = r$ .
- Substituting $p$ with $\mathrm T$ , $q=\mathrm T$ and $r = \mathrm T = p$ .
- Substituting $p$ with $\mathrm F$ , $q=\mathrm F$ and $r = \mathrm F = p$ .
Therefore, $p = r$ , as required.

Finally, we can prove the commutativity and associativity property of conjunction.

Theorem 2. Let $p, q, r$ be propositional variables. Then the following hold.

$\begin{aligned} p \wedge q = q \wedge p, \quad (p \wedge q) \wedge r = p \wedge (q \wedge r). \end{aligned}$

Proof. For the first result, use a truth table argument. For the second result, when we substitute $p$ with $\mathrm T$ , we have $p = t$ with respect to $q$ , so that by chaining equalities,

$(p \wedge q) \wedge r = (t \wedge q) \wedge r = q \wedge r = t \wedge (q \wedge r) = p \wedge (q \wedge r) .$

We get the same result when substituting $p$ with $\mathrm F$ .

There is more to say about propositional logic, such as disjunctions and even argument forms, but this post is getting as long as it needs to. Crucially, we have implemented the core elements of propositional logic which we can take advantage of in future topics.

—Joel Kindiak, 15 Nov 24, 2359H
January 9, 2025

logic, math, mathematics, Probability, research
Dividing Your Power

This problem is such an interesting one that, just like a previous problem, was given in an exam, but broken down into more palatable steps.

Problem 1. Prove that there are infinitely many positive even integers $n$ such that $n \mid (2^n + 2)$ and $(n - 1) \mid (2^n+1)$ .

(Click for Solution)

Solution. Consider $n_1 = 2$ , which satisfies the property since $2 \mid (2^2 + 2)$ and $(2-1) \mid (2^2+1)$ trivially. The core idea is to inductively define $n_{i + 1}$ in terms of $n_i$ so that both integers satisfy $n_i \mid (2^{n_i} + 2)$ and $(n_i - 1) \mid (2^{n_i} +1)$ .

To that end, for any even $n_i = n$ such that $n \mid (2^n + 2)$ and $(n - 1) \mid (2^n+1)$ , define $n_{i+1} = m := 2^n + 2$ . We claim that $m \mid (2^m + 2)$ and $(m - 1) \mid (2^m+1)$ . By definition of $m$ , we observe that

$\displaystyle 2^m + 2 = 2\times (2^{m-1} + 1) = 2 \times (2^{2^n + 1} + 1).$

Since $(n - 1) \mid (2^n +1)$ , find an integer $k$ such that $2^n + 1 = k(n-1)$ . Since the left-hand side is odd, the right-hand side must be odd, so that $k$ is odd. Thus,

$2^{2^n + 1} + 1 = 2^{(n-1)k} + 1 = (2^{n-1})^k + 1.$

Consider the function $x^k + 1$ . Since $(-1)^k + 1 = 0$ , by the factor theorem, $(x+1)$ is a factor of $(x^k+1)$ . In particular, $(2^{n-1} + 1) \mid ((2^{n-1})^k + 1)$ . Let $l$ denote an integer such that

$(2^{n-1})^k + 1 = (2^{n-1} + 1)l.$

Combining our results,

$2^m + 2 = 2 \times (2^{2^n + 1} + 1) = 2 \times (2^{n-1} + 1)l = (2^n + 2) l = ml,$

so that $m \mid (2^m + 2)$ . For the second result,

$2^m + 1 = 2^{2^n + 2} + 1.$

Since $n \mid (2^n + 2)$ , find an integer $r$ such that $2^n + 2 = nr$ so that

$2^{2^n + 2} + 1 = 2^{nr} + 1 = (2^n)^r + 1.$

Since $n$ is even, find an integer $s$ such that $n = 2s$ . Then

$\displaystyle 2^n + 2 = nr = 2sr \quad \Rightarrow \quad 2^{n-1} + 1 = sr.$

Since the left-hand side is odd, so is the right-hand side, and in particular, so is $r$ . Therefore,

$m-1 = (2^n + 1) \mid ((2^n)^r + 1) = 2^m + 1,$

as required. Finally, we have found some infinitely many integers $n = n_1,n_2,\dots$ such that $n \mid (2^n + 2)$ and $(n - 1) \mid (2^n+1)$ .

—Joel Kindiak, 13 Nov 24, 1813H

November 27, 2024

ai, cryptography, math, mathematics, number-theory
When Integrals Approximate One

In the following problems, let $f$ be a function that is continuous on $\mathbb R$ .

Problem 1. Given that $\displaystyle \lim_{x \to \infty} \frac{1}{x} \int_0^x f(t)\, \mathrm dt = 1$ , prove that $\displaystyle \lim_{x \to \infty} f(x) = 1$ if the limit exists.

(Click for Solution)

Solution. We first claim that $\displaystyle \int_0^x f(t)\, \mathrm dt \to \infty$ . Fix $M > 0$ . By hypothesis, for any $\epsilon > 0$ , there exists $K > 0$ such that $x > K$ implies

$\displaystyle \left|\frac{1}{x} \int_0^x f(t)\, \mathrm dt - 1\right| < \epsilon \quad \Rightarrow \quad \int_0^x f(t)\, \mathrm dt > (1 - \epsilon)x.$

Setting $\epsilon = 1/2$ , choose $N := \max\{K, 2M\}$ so that $x > N$ implies

$\displaystyle \int_0^x f(t)\, \mathrm dt > (1-1/2) \cdot 2M = M.$

Therefore $\displaystyle \int_0^x f(t)\, \mathrm dt \to \infty$ . By L’Hôpital’s rule and the fundamental theorem of calculus,

$\displaystyle \lim_{x \to \infty} f(x) = \lim_{x \to \infty} \frac{\frac{\mathrm d}{\mathrm dx} \int_0^x f(t)\, \mathrm dt}{\frac{\mathrm d}{\mathrm dx} (x)} = \lim_{x \to \infty} \frac{\int_0^x f(t)\, \mathrm dt}{x} = 1.$

But what if we don’t know that the limit exists? The added feature of $f$ being increasing helps.

Problem 2. Given that $\displaystyle \lim_{x \to \infty} \frac{1}{x} \int_0^x f(t)\, \mathrm dt = 1$ , prove that $\displaystyle \lim_{x \to \infty} f(x) = 1$ if $f$ is increasing.

(Click for Solution)

Solution. Fix $\epsilon > 0$ . By the given condition, for any $k > 0$ to be chosen, there exists $K > 0$ such that for $x > K$ ,

$\displaystyle -k \epsilon < \frac{1}{x} \int_0^x f(t)\, \mathrm dt - 1 < k \epsilon.$

We claim that $f(x) \leq 1$ for any $x$ . Suppose $f(N) > 1$ for some $N$ . Define $\epsilon_0 := (f(N)-1)/2$ so that for $x > N$ , $f(x) \geq f(N) > 1 + \epsilon_0$ . Then

$\displaystyle \begin{aligned} \frac{1}{x} \int_0^x f(t)\, \mathrm dt &= \frac{1}{x} \int_0^N f(t)\, \mathrm dt + \frac{1}{x} \int_N^x f(t)\, \mathrm dt \\ &\geq \frac{1}{x} \int_0^N f(t)\, \mathrm dt + (1+\epsilon_0) (1-N/x) \\ &\geq \frac{N}{x} \cdot (f(0) - (1+\epsilon_0)) + (1+\epsilon_0) . \end{aligned}$

Taking $x \to \infty$ yields

$\displaystyle 1 = \lim_{x \to \infty} \frac{1}{x} \int_0^x f(t)\, \mathrm dt \geq 0 \cdot (f(0) - (1+\epsilon_0)) + (1+\epsilon_0) > 1,$

a contradiction. Therefore, $f(x) \leq 1$ for any $x$ . On the other hand, apply the mean value theorem and the fundamental theorem of calculus to find $c \in (0, x)$ such that

$\displaystyle f(c) = \frac{1}{x} \int_0^x f(t)\, \mathrm dt > 1 - k\epsilon.$

Setting $k = 1$ and using the fact that $f$ is increasing,

$1 - \epsilon < f(c) \leq f(x) \leq 1 < 1 +\epsilon\quad \Rightarrow \quad |f(x) - 1| < \epsilon.$

It turns out that we can we relax our hypothesis. However, this will require more rudimentary ideas.

Problem 3. Given that $\displaystyle \lim_{x \to \infty} \frac{1}{x} \int_0^x f(t)\, \mathrm dt = 1$ , prove that $\displaystyle \lim_{x \to \infty} f(x) = 1$ .

(Click for Solution)

Solution. Fix $\epsilon > 0$ . By the given condition, for any $k > 0$ to be chosen, there exists $K > 0$ such that for $x > K$ ,

$\displaystyle -k \epsilon < \frac{1}{x} \int_0^x f(t)\, \mathrm dt - 1 < k \epsilon.$

By algebra, since $x > K > 0$ ,

$\displaystyle -k \epsilon x < \int_0^x f(t)\, \mathrm dt - x < k \epsilon x.$

In particular, the inequality holds replacing $x$ with $x+h$ for $|h| < (x-K)/2$ so that

$\displaystyle -k \epsilon (x+h) < \int_0^{x+h} f(t)\, \mathrm dt - (x+h) < k \epsilon (x+h).$

Subtracting the inequalities then dividing by $h$ ,

$\displaystyle -k \epsilon < \frac 1h \int_x^{x+h} f(t)\, \mathrm dt - 1 < k \epsilon.$

Taking $h \to 0$ and applying the fundamental theorem of calculus,

$\displaystyle -k \epsilon \leq f(x)-1 \leq k \epsilon.$

Setting $k = 1/2$ ,

$\displaystyle -\epsilon < -k \epsilon \leq f(x)-1 \leq k \epsilon < \epsilon\quad \Rightarrow \quad |f(x) - 1| < \epsilon.$

By the $\epsilon$ – $K$ definition for limits, $\displaystyle \lim_{x \to \infty} f(x) = 1$ .

—Joel Kindiak, 26 Nov 24, 0110H

November 26, 2024

Calculus, machine-learning, math, mathematics, physics
What Makes Strong Induction Strong?
In introductory discrete mathematics, we are introduced to a powerful proof technique called the principle of mathematical induction, which is commonly formulated as follows.

Mathematical Induction. Let $\phi$ be a predicate on $\mathbb N$ . Suppose $\phi(0)$ and for any $k \in \mathbb N$ , $\phi(k) \Rightarrow \phi(k+1)$ . Then for any $n \in \mathbb N$ , $\phi(n)$ .

Proof of Mathematical Induction. Let $K := \{n \in \mathbb N : \phi(n)\} \subseteq \mathbb N$ . By the first condition, $0 \in K$ . By the second condition, we obtain the equivalent formulation $k \in K \Rightarrow k+1 \in K$ . By a core property of $\mathbb N$ , $K = \mathbb N$ .

The condition $\phi(0)$ is known as the base case and the condition “for any $k \in \mathbb N$ , $\phi(k) \Rightarrow \phi(k+1)$ ” is known as the induction step. Students are introduced to a stronger variant of induction known as strong induction.

Strong Induction. Let $\phi$ be a predicate on $\mathbb N$ . Suppose $\phi(0)$ and for any $k \in \mathbb N$ , $\phi(0),\phi(1),\dots,\phi(k) \Rightarrow \phi(k+1)$ . Then for any $n \in \mathbb N$ , $\phi(n)$ .

The difference here is that we have more tools to work with. We will use strong induction to prove the existence part of the fundamental theorem of arithmetic.

Proof of Strong Induction. Suppose $\phi(0)$ and for any $k \in \mathbb N$ , $\phi(0),\phi(1),\dots,\phi(k) \Rightarrow \phi(k+1)$ . Let $\Phi$ be the predicate defined on $\mathbb N$ by

$\Phi(n) = (\forall k\in \mathbb N\quad (k \leq n \ \Rightarrow \ \phi(k))).$

We will use standard induction to prove that for any $n\in \mathbb N$ , $\Phi(n)$ . Since $n \leq n$ , this implies $\phi(n)$ , as required.

For the base case, fix $k \in \mathbb N$ such that $k \leq 0$ . Then $k = 0$ , and by the first condition, $\phi(k) = \phi(0)$ holds. Therefore, $\Phi(0)$ .

For the induction step, fix $k \in \mathbb N$ and suppose $\Phi(k)$ . By definition, for any $m \in \mathbb N$ , $m \leq k$ implies $\phi(m)$ . Therefore, $\phi(0),\phi(1),\dots,\phi(k)$ . By the second condition, $\phi(k+1)$ . Therefore, for any $m \in \mathbb N$ , $m \leq k+1$ implies $\phi(m)$ . This is equivalent to $\Phi(k+1)$ . Therefore, $\Phi(k+1)$ , as required.

Therefore, $\Phi(0)$ and for any $k \in \mathbb N$ , $\Phi(k)$ implies $\Phi(k+1)$ . By induction, for any $n \in \mathbb N$ , $\Phi(n)$ , as required.

As promised, we prove that every natural number can be factored into a unique product of primes.

Fundamental Theorem of Arithmetic. For any number $n \in \mathbb N$ such that $n \geq 2$ , there exist primes $p_1,\dots,p_N$ such that

$\displaystyle n = p_1 \cdots p_N = \prod_{k=1}^N p_k.$

Furthermore, the factorisation is unique in the following sense: if $p_1 \leq \dots \leq p_N$ and $q_1 \leq \dots \leq q_M$ are primes such that

$\displaystyle n = \prod_{i=1}^N p_i = \prod_{j=1}^M q_j,$

then $M=N$ and for any $1 \leq i \leq N$ , $p_i = q_i$ .

Proof of the Fundamental Theorem of Arithmetic. We will use strong induction to establish existence. Let $\phi$ be a predicate on $\mathbb N$ defined by $\phi(n)$ precisely when $n + 2$ can be factored into primes. Clearly, $0 +2 = 2$ is factored into the prime $2$ , so that $\phi(0)$ . Suppose for any $k \in \mathbb N$ , $\phi(0),\phi(1),\dots,\phi(k)$ . We need to establish $\phi(k+1)$ .

Consider the number $k+1 +2 = k +3$ . There are two cases. Either $k+3$ is prime, or not. If $k+3$ is prime, then it is factored into $k+3$ , as required. If $k+3$ is not prime, then $k+3$ is composite. This means that there exist positive integers $r, s \geq 2$ such that $k+3 = rs >\max\{r, s\}$ . Since $2 \leq r, s < k+1+2$ , by the induction hypothesis, there exist primes $p_i$ and $q_j$ such that

$\displaystyle r = \prod_{i = 1}^N p_i,\quad s = \prod_{j = 1}^M q_j.$

Hence, letting $r_l$ denote the primes in non-decreasing sequence,

$\displaystyle k+3 = rs = \prod_{i = 1}^N p_i \cdot \prod_{j = 1}^M q_j = \prod_{l = 1}^{M+N} r_l,$

as required. Therefore, for any $n \in \mathbb N$ , $\phi(n)$ . This is equivalent to the original existence proposition.

We will use Euclid’s lemma to establish uniqueness, for the sake of completeness. As an aside, Euclid’s lemma will be proved independently from the fundamental theorem of arithmetic, so that we do not incur a circular-reasoning fallacy.

Suppose $p_1 \leq \dots \leq p_N$ and $q_1 \leq \dots \leq q_M$ are primes such that

$\displaystyle n = \prod_{i=1}^N p_i = \prod_{j=1}^M q_j.$

We claim that $p_1 = q_1$ . Repeating the argument $\min\{N,M\}$ times then yields the result. Fix $i$ . By Euclid’s lemma, there exists $j$ such that $p_i \mid q_j$ . Thus, there exists some integer $k$ such that $q_j = kp_i$ . Since $q_j$ is prime, $q_j \mid k$ or $q_j \mid p_i$ .
- If $q_j \mid k$ , find an integer $l$ such that $k = q_j l$ . Then $q_j = kp_i = q_j l p_i \Rightarrow lp_i = 1 \Rightarrow p_i = 1$ , a contradiction.
- If $q_j \mid p_i$ , then a similar argument yields $p_i = q_j$ .
Next, we show that $p_1 = q_1$ . Otherwise, there exists $j$ such that $q_1 < q_j = p_1$ . By Euclid’s lemma again, there exists $i$ such that $q_1 \mid p_i$ . A similar argument yields $q_1 = p_i \geq p_1 > q_1$ , a contradiction.

To conclude, strong induction affords us not just $\phi(k)$ , from which we need to prove $\phi(k+1)$ , but furthermore the whole sleuth of $\phi(0),\phi(1),\dots,\phi(k)$ , using any of which or even any combination thereof, to prove $\phi(k+1)$ .

Strong induction even helps us reason about the well-ordering principle, and we need that principle to establish long division. We do that next time.

—Joel Kindiak, 13 Nov 24, 0017H
November 13, 2024

machine-learning, math, mathematics, number-theory, Probability
The Overrated L’Hôpital’s Rule

I will double down on the title of this post. L’Hôpital’s rule is useful, but gets too much attention from popular science meme pages. Furthermore, I have not seen a meaningful application of L’Hôpital’s rule other than mathematical flexing (that gets very quickly humbled in real analysis).

Nevertheless, perhaps I can suggest a proof of the simplified version of L’Hôpital’s rule, using Cauchy’s mean value theorem. Here’s the motivation behind this result.

Let $f, g$ be real-valued functions continuous on $[a, b]$ and differentiable on $(a, b)$ . Suppose $g(a) \neq g(b)$ and $g' \neq 0$ . Using the mean value theorem, find $c_1,c_2 \in (a, b)$ such that

$\displaystyle \frac{f(b) - f(a)}{g(b) - g(a)} = \frac{f'(c_1)(b-a)}{g'(c_2)(b-a)} = \frac{f'(c_1)}{g'(c_2)}.$

Cauchy’s mean value theorem asserts a stronger claim: we can find $c$ such that $c_1 = c_2 = c$ .

Theorem 1 (Cauchy’s Mean Value Theorem). Let $f, g$ be real-valued functions continuous on $[a, b]$ and differentiable on $(a, b)$ . Suppose $g(a) \neq g(b)$ and $g' \neq 0$ on $(a, b)$ . Then there exists $c \in (a, b)$ such that

$\displaystyle \frac{f(b)-f(a)}{g(b)-g(a)} = \frac{f'(c)}{g'(c)}.$

Observe that $g(x) = x$ yields the vanilla mean value theorem.

Proof. Define $h : [a, b] \to \mathbb R$ by

$\displaystyle h(x) := f(x) - f(a) - \frac{f(b)-f(a)}{g(b)-g(a)} \cdot (g(x) - g(a)),$

where $h$ is continuous, and $h'$ is differentiable on $(a, b)$ . In fact,

$\displaystyle h'(x) = f'(x) - \frac{f(b)-f(a)}{g(b)-g(a)} \cdot g'(x).$

Since $h(a) = h(b) = 0$ , by Rolle’s theorem, there exists $c \in (a, b)$ such that $h'(c) = 0$ :

$\displaystyle 0 = h'(c) = f'(c) - \frac{f(b)-f(a)}{g(b)-g(a)} \cdot g'(c).$

Algebra yields the desired result.

Now, we will prove a special case of L’Hôpital’s rule for limits of the form $0/0$ as $x\to 0$ .

Theorem 2 (L’Hôpital’s Rule). Let $f,g$ be differentiable at $0$ and $f(0) = g(0) = 0$ . Suppose $g' \neq 0$ for points near $0$ and $f'(h)/g'(h) \to L$ as $h \to 0$ . Then $f(h)/g(h) \to L$ as $h \to 0$ .

Proof. For any sufficiently small $h$ , use Cauchy’s mean value theorem to find $c_h$ between $0$ and $x$ such that

$\displaystyle \frac{f(h)}{g(h)} = \frac{f(h) - f(0)}{g(h) - g(0)} = \frac{f'(c_h)}{g'(c_h)} = L + o(1),$

where the last equation holds since $c_h \to 0$ as $h \to 0$ .

We can finally proceed to integration.

—Joel Kindiak, 31 Oct, 1531H

October 31, 2024

geometry, limits, math, mathematics, Topology
Profit Maximisation for Math People
When I had to learn economics in high school, I struggled tremendously due to its language-based emphasis (which meant tons of essay-writing with arguably subjective marking schemes).

Yet, I remember how one teaching intern scribbled some equations to prove them mathematically, and those equations were my only takeaways from the entire two years of economics. I’m convinced that economics without equations is gravely incomplete. Equivalently, what this means is that when we include the mathematics with the economic theory, the concepts therein start to illuminate meaning.

Here’s one of my favourite results in economics.

Theorem 1. A firm maximises profit when its marginal revenue (MC) equals its marginal cost (MC) and when the marginal cost is increasing.

Here’s a layperson’s justification for this theorem.

If the firm is producing at a quantity where MR > MC, then it can increase profit by increasing output. The reason is since the marginal revenue exceeds the marginal cost, additional output is adding more to profit than it is taking away. If the firm is producing at a quantity where MC > MR, then it can increase profit by reducing output.
Adapted from Lumen Learning

Technically, this explanation can make sense, but I was absolutely confused to pieces by it. Don’t even get me started on having to regurgitate this paragraph compounded with my atrocious handwriting when answering essay-based questions. Let’s define our terms then prove this mathematically.

Definition. Let $x$ denote the quantity of a product that a firm produces. Make the following notations:
- $R(x)$ : the revenue the firm earns by selling $x$ units of such a product,
- $C(x)$ : the cost the firm incurs by producing $x$ units of such a product,
- $\pi(x)$ : the profit the company earns by selling $x$ units of the product.
It is intuitive that $\pi = R - C$ . Note that we are adopting economists’ convention to denote profit by $\pi$ , not to be confused with the circle constant $3.14159\dots$ .

Equivalently, we define the marginal revenue function and marginal cost function by $\mathrm{MR} := R'$ and $\mathrm{MC} := C'$ respectively.

Now, onto the proof, using the derivative tests that we have previously developed. We will assume that $\mathrm{MR}$ is strictly decreasing, though that actually can be proven from more fundamental principles of economics.

Proof of Theorem 1. To maximise profit at the output level $c$ , we need $\pi'(c) = 0$ . Since $\pi = R - C$ , this implies that

$\displaystyle 0=\pi'(c) = (R-C)'(c) = R'(c) - C'(c) = \mathrm{MR}(c) - \mathrm {MC}(c).$

By algebra, $\mathrm{MR}(c) = \mathrm{MC}(c)$ . Assuming that $\mathrm{MC}$ is decreasing so that $\mathrm{MC}'(c) \leq 0$ ,

$\pi''(c) = \mathrm{MR}'(c) - \mathrm{MC}'(c) < 0 - 0 = 0.$

By the second derivative test, $c$ is a local maximum for $\pi$ .

We could have many more economics-contextualised applications of differential calculus, but perhaps another time.

For now, we shift gears and discuss the overrated l’Hôpital’s rule.

—Joel Kindiak, 31 Oct 24, 1402H
October 31, 2024

ai, machine-learning, math, mathematics, Probability
Technical Optimisation
One of the most practical uses of differential calculus is to optimise desired quantities, which amounts to either minimising a function $f(x)$ on some subset $I \subseteq \mathbb R$ , or maximising it. How do we do that?

Let’s first formulate the notion of a global minimum and local minimum respectively.

Definition 1. Let $I \subseteq \mathbb R$ and $f : I \to \mathbb R$ be a function.
- We say that $(c, f(c))$ is a global minimum point of $f$ on $I$ if for any $x \in I$ , $f(x) \geq f(c)$ .
- We say that $(c, f(c))$ is a local minimum point of $f$ if there exists $\delta > 0$ such that $(c, f(c))$ is a global minimum point on $(c - \delta , c + \delta) \cap I$ .
To abbreviate, we will say that $c$ is a global (resp. local) minimum point of $f$ .

In a symmetric manner, we can define the global maximum and local maximum respectively.

We say that $c$ is a global (reap. local) extremum if it is either a global (resp. local) minimum or a global (resp. local) maximum. Since differentiable functions on an interval are continuous on that interval, by the extreme value theorem, we will always obtain a global extremum. In fact, we have the following symmetrical result.

Lemma 1. Suppose that $c$ is a global (resp. local) maximum for a function $f$ . Then $c$ is a global (reap. local) minimum for $-f$ .

Proof. Employ the equivalence of $f(x) \geq f(c) \iff -f(x) \leq -f(c)$ .

What about a local extremum?

Theorem 1. Let $f$ be a function that is differentiable at $c$ . Suppose $c$ is a local extremum at $f$ . Then $f'(c) = 0$ .

Proof. The proof of this result is essentially the same as that of Rolle’s theorem.

Since global and local extrema constitute all possible extremum points, we have the critical value test.

Theorem 2. Let $f: [a, b] \to \mathbb R$ be a continuous function that is differentiable on $(a, b)$ . Then $f$ obtains global extrema either at $a, b$ or interior points $c$ such that $f'(c)$ is undefined or $f'(c) = 0$ . These possible points are known as critical points.

Does the converse hold? That is, does $f'(c) = 0$ imply that $c$ is a local extremum? Not if we consider $c = 0$ and the function $f(x) = x^3$ . How then do we determine the nature of this stationary point?

Suppose $f'(c) = 0$ . Denote $f'(c^-) \leq 0$ (resp. $f'(c^+) \geq 0$ ). to mean that there exists $\delta > 0$ such that for any $x \in (c-\delta, c)$ (resp. $x \in (c, c + \delta)$ ), $f'(x) \leq 0$ (resp. $f'(x) \geq 0$ ). We can use the first derivative test to answer our aforementioned question.

Theorem 3 (First Derivative Test). Let $f : [a, b] \to \mathbb R$ be differentiable at $c \in (a, b)$ . Suppose $f'(c) = 0$ .
- If $f'(c^-) \leq 0$ and $f'(c^+) \geq 0$ , then $c$ is a local minimum of $f$ .
- If $f'(c^-) \geq 0$ and $f'(c^+) \leq 0$ , then $c$ is a local maximum of $f$ .
- If $f'(c^-), f'(c^+) \geq 0$ or $f'(c^-),f'(c^+) \geq 0$ , then $c$ is not a local extremum. In this case, we say that $c$ is a stationary point of inflection.
Proof. We will prove the first result.
- Since $f'(c^-) \leq 0$ , find $\delta_1 > 0$ such that for $x \in (c - \delta_1, c)$ , $f'(x) \leq 0$ .
- Since $f'(c^+) \geq 0$ , find $\delta_2 > 0$ such that for $x \in (c, c + \delta_2)$ , $f'(x) \geq 0$ .
Define $\delta := \min\{\delta_1,\delta_2\}$ . We claim that for any $x \in (c-\delta, c+\delta)$ , $f(x) \geq f(c)$ .

Suppose $x < c$ . By the mean value theorem, there exists

$c_1 \in (x,c) \subseteq (c-\delta, c) \subseteq (c-\delta_1,c),$

implying $f'(c_1) \leq 0$ , such that

$\displaystyle f(c) = f(x) + f'(c_1) ( c - x) \leq f(x) + 0 \cdot 0 = f(x).$

A similar argument for $x > c$ yields

$f(x) = f(c) + \underbrace{(\text{stuff})}_{\geq 0} \underbrace{(x-c)}_{> 0} \geq 0.$

Can we have a simpler computation for this process? Yes, but this does not help us with inflection points. Furthermore, we can make no conclusion if $f''(c) = 0$ .

Theorem 4 (Second Derivative Test). Let $f : [a, b] \to \mathbb R$ be twice-differentiable at $c \in (a, b)$ . Suppose $f'(c) = 0$ .
- If $f''(c) > 0$ , then $c$ is a local minimum of $f$ .
- If $f''(c) < 0$ , then $c$ is a local maximum of $f$ .
- If $f''(c) = 0$ , the test is inconclusive.
Proof. We will prove the first result since the second result follows by symmetry.

By the definition of differentiation, for sufficiently small $h > 0$ ,

$\displaystyle \frac{f'(c+h)}{h}=\frac{f'(c+h) - f'(c)}{h} = f''(c) + o(h) > 0.$

Hence, $f'(c+h) > (f''(c) + o(h)) \cdot h > 0$ , which after taking $h \to 0^+$ , implies that $f'(c^+) \geq 0$ . Likewise, from the left side,

$\displaystyle \frac{-f'(c-h)}{h}=\frac{f'(c) - f'(c-h)}{h} = f''(c) + o(h) > 0,$

which yields $-f'(c^-) \leq 0 \iff f'(c^-) \geq 0$ .

For the last result, consider the functions $x^4$ for $0$ being a local minimum, $-x^4$ for $0$ being a local maximum, and $x^3$ for $0$ being a stationary point of inflection since in all cases, $f''(0) = 0$ .

In the next post, we will use this test to maximise profit.

—Joel Kindiak, 31 Oct 24, 1316H
October 31, 2024

math, mathematics, physics, Probability, sine