The set of all positive integers ${1, 2, 3, …}$ are natural numbers, denoted by $\N$.
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 $.
A proposition is a mathematical statement, usually denoted by $P$.
$P(n) $ is a proposition about $n$.
N5'. Every nonempty subset of $\N$ has a minimal element.
by strong induction
</span>
</span>
<span class="proof__expand"><a>[expand]</a></span>
N1 - N4, N5 $\iff$ N1 - N4, N5'
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 $.
Prove that N1 - N4, N5 $\implies$ $\forall x \in X, x \neq 1$ is a successor in $X $.
</span>
</span>
<span class="proof__expand"><a>[expand]</a></span>
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:
- The base case: prov that the statement holds for the first natural number $n_1 $.
- 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.
$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) $.
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:
- The base case: prov that the statement holds for the first natural number $n_1 $.
- The inductive step: assume the statement holds for all natural numbers $\leq n$, and prove that then the statement holds for $n + 1 $.
Try to prove that $N1 - N4, N5 \iff N1, …, N4, N5' $
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.
$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)$.