$\newcommand{\br}{\\}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\P}{\mathbb{P}}$ $\newcommand{\F}{\mathbb{F}}$ $\newcommand{\L}{\mathcal{L}}$ $\newcommand{\spa}[1]{\text{span}(#1)}$ $\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\emptyset}{\varnothing}$ $\newcommand{\otherwise}{\text{ otherwise }}$ $\newcommand{\if}{\text{ if }}$ $\newcommand{\proj}{\text{proj}}$ $\newcommand{\union}{\cup}$ $\newcommand{\intercept}{\cap}$ $\newcommand{\abs}[1]{| #1 |}$ $\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$ $\newcommand{\pare}[1]{\left\(#1\right\)}$ $\newcommand{\t}[1]{\text{ #1 }}$ $\newcommand{\head}{\text H}$ $\newcommand{\tail}{\text T}$ $\newcommand{\d}{\text d}$ $\newcommand{\limu}[2]{\underset{#1 \to #2}\lim}$ $\newcommand{\inv}[1]{{#1}^{-1}}$ $\newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $\newcommand{\nullity}[1]{\text{nullity}(#1)}$ $\newcommand{\rank}[1]{\text{rank }#1}$ $\newcommand{\var}[1]{\text{var}(#1)}$ $\newcommand{\tr}[1]{\text{tr}(#1)}$ $\newcommand{\oto}{\text{ one-to-one }}$ $\newcommand{\ot}{\text{ onto }}$ $\newcommand{\Re}[1]{\text{Re}(#1)}$ $\newcommand{\Im}[1]{\text{Im}(#1)}$ $\newcommand{\Vcw}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Vce}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Vcr}[4]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \end{bmatrix}}$ $\newcommand{\Vct}[5]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{bmatrix}}$ $\newcommand{\Vcy}[6]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \end{bmatrix}}$ $\newcommand{\Vcu}[7]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \br #7 \end{bmatrix}}$ $\newcommand{\vcw}[2]{\begin{matrix} #1 \br #2 \end{matrix}}$ $\newcommand{\vce}[3]{\begin{matrix} #1 \br #2 \br #3 \end{matrix}}$ $\newcommand{\vcr}[4]{\begin{matrix} #1 \br #2 \br #3 \br #4 \end{matrix}}$ $\newcommand{\vct}[5]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \end{matrix}}$ $\newcommand{\vcy}[6]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \end{matrix}}$ $\newcommand{\vcu}[7]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \br #7 \end{matrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Mqr}[4]{\begin{bmatrix} #1 & #2 & #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqt}[5]{\begin{bmatrix} #1 & #2 & #3 & #4 & #5 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mrq}[4]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \end{bmatrix}}$ $\newcommand{\Mtq}[5]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{bmatrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Mww}[4]{\begin{bmatrix} #1 & #2 \br #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mwe}[6]{\begin{bmatrix} #1 & #2 & #3\br #4 & #5 & #6 \end{bmatrix}}$ $\newcommand{\Mew}[6]{\begin{bmatrix} #1 & #2 \br #3 & #4 \br #5 & #6 \end{bmatrix}}$ $\newcommand{\Mee}[9]{\begin{bmatrix} #1 & #2 & #3 \br #4 & #5 & #6 \br #7 & #8 & #9 \end{bmatrix}}$
Definition: Natural Numbers $\N$

The set of all positive integers ${1, 2, 3, …}$ are natural numbers, denoted by $\N$.

Axioms: Peano Axioms (Peano Postulates)

N1. $1$ belongs to $\N $.

N2. If $n$ belongs to $\N$ then its successor $n + 1$ belongs to $\N$.

N3. $1$ is not the successor of any element in $\N$.

N4. If $n$ and $m$ in $\N$ have the same successor, then $n = m$.

N5. (Principal of Induction) A subset of $\N $ which contains $1$, and which contains $n + 1$ whenever it contains $n $, must equal $\N $.

Definition: Proposition

A proposition is a mathematical statement, usually denoted by $P$.

$P(n) $ is a proposition about $n$.

Theorem : Well-Ordering Principle of Natural Numbers

N5’. Every nonempty subset of $\N$ has a minimal element.

Proof by strong induction [expand]

Let $A$ be a non-empty subset of $\N $. Want to know that $A $ has a minimal element, that is, there is an element $a \in A $ such that $a \leq n $ for all $n \in A $. We will do this by strong induction on the following predicate:

$$P(n): \text{If }n \in A\text{, then }A\text{ has a minimal element.} $$

the base case: $P(0)$ is clearly true, since $0 \leq n \forall n \in N $.

the inductive step: Want to show that $[P(0) \land P(1) \land P(2) \land … \land P(n)] \to P(n + 1)$.

To this end, suppose that $P(0), P(1), …, P(n) $ are all true and that $n + 1 \in A$. We consider two cases.

CASE 1: $\neg \exists m (m \in A \land m < n + 1) $

In this case, $n + 1$ is the least element of $A$.

CASE 2: $\exists m (m \in A \land m < n + 1) $

In this case, since $P(m)$ is true, $A$ has a least element.

Either way, we conclude that $P(n + 1)$ is true.

So, by strong mathematical induction, we obtain that $P(n) $ is true for all $n \in N$. Since $A $ is not empty, we can pick an $n \in A $. Moreover, since $P(n) $ is true, this implies that $A $ has a least element.

N1 - N4, N5 $\iff$ N1 - N4, N5’

Corollary

O1. For $a,b \in \N, a \leq b $ or $b \leq a $.

O2. $a \leq b, b \leq a \implies a = b $.

O3. $a \leq b, b \leq c \implies a \leq c $.

Example

Prove that N1 - N4, N5 $\implies$ $\forall x \in X, x \neq 1$ is a successor in $X $.

Proof [expand]

Let $X$ be a subset of $\N$,

Assume that $x \neq 1$ and $x$ not a successor.

Let $X$ be a set of $\set{ 1 } \cup \set{ \text{all successors}} = \N$ by N5.

Then $x \in X , x \neq 1$ is CONTRADICTION; $x$ is a successor.

Definition: Mathematical Induction

Mathematical induction is a mathematical proof technique used to prove that a property $P(n)$ holds for every natural number $n$.

The proof consists of two steps:

  1. The base case: prov that the statement holds for the first natural number $n_1 $.
  2. The inductive step: assume the statement holds for some natural number $n $, and prove that then the statement holds for $n + 1 $.

The hypothesis in the inductive step, that the statement holds for some $n$, is called the induction hypothesis or inductive hypothesis.

Example: Mathematical induction

$P(n) = 1 + 3 + 5 + … + 2n - 1 = n^2$

$P(1) = 1 = 1^2$

$P(2) = 1 + 3 = 4 = 2^2 $

Assume $P(n)$:

Then $1 + 3 + 5 + … + 2n -1 = n^2 $

$1 + 3 + 5 + … + 2n + 1 = n^2 + 2n + 1 $

$1 + 3 + 5 + … + (2(n+1) - 1) = (n+1)^2 $

So $\P(n) \implies \P(n+1) $.

Definition: Complete Induction (Strong Induction)

Complete induction is a variant of mathematical induction which has a stronger inductive hypothesis. The hypothesis assumes that $P(n) $ holds for all natural $n $ less than or equals to $n$.

The proof still consists of two steps:

  1. The base case: prov that the statement holds for the first natural number $n_1 $.
  2. The inductive step: assume the statement holds for all natural numbers $\leq n$, and prove that then the statement holds for $n + 1 $.
Example

Try to prove that $N1 - N4, N5 \iff N1, …, N4, N5’ $

Example: Prime factorization

Every $n \in \N$ is a product of primes.

Let $P(n)$: $n$ is a product of primes.

Assume $P(m)$ is product of primes for all $m \leq n $.

For $n + 1$,

if $n+1$ prime, then $n + 1$ is a product of prime.

if $n+1$ not prime (composite), then $n + 1 = a \cdot b$ for some $a, b \in \N$, $a,b > 1$.

$\therefore$ by complete induction

$$a = p_1, p_2, …, p_{ k } $$

$$b = q_1, q_2, …, q_{ l } $$

$\therefore n + 1 = ab = p_1 p_2 … p_{ k } q_1 q_2 … q_{ l } $

$\therefore P(n + 1)$

Note: For $P(1)$, allow $1 $ to be a prime.

Example

$P(n): \abs{ \sin(nx)} \leq n \abs{ \sin(x)} $

If $n = 1$, $\abs{ \sin (1 x)} \leq 1 \abs{ \sin x }$

Assume $P(n)$ consider

$\abs{ \sin ((n + 1) x)} = \abs{ \sin nx \cos x + \cos nx \sin x}$

$\abs{ a + b } \leq \abs{ a } + \abs{ b }$(triangle inequality)

$\therefore $

$\begin{align*} \abs{ \sin((n+1)x)} &\leq \abs{ \sin nx \cos x } + \abs{ \cos nx \sin x } \br & \leq \abs{ \sin nx } \abs{ \cos x } + \abs{ \cos nx } \abs{ \sin x } \br & \leq \abs{ \sin nx } \cdot 1 + 1 \cdot \abs{ \sin x } \br & \leq n \abs{ \sin x } + \abs{ \sin x } = (n+1) \abs{ \sin x } \end{align*}$

$\therefore P(n + 1)$.