Induction Proofs

The following all follow from the third axiom in the definition of and are equivalent:

1. Mathematical Induction: If a property $\Phi(x)$ holds for $x=0$ and if the implication $\Phi(n)\rightarrow \Phi(n+1)$ holds, then $\Phi(x)$ holds for all $x\in \ensuremath{\mathbb{N}}$.
2. Strong induction: If a property $\Phi(x)$ holds for $x=0$ and if the implication $(\forall_{k<n}\Phi(k))\rightarrow \Phi(n)$ holds, then $\Phi(x)$ holds for all $x\in \ensuremath{\mathbb{N}}$.
3. Well ordering of : Any non-empty subset $S\subseteq \ensuremath{\mathbb{N}}$ has a least element.

If a mathematician uses ``...'' in the middle of an informal argument, it is a good bet that there is an induction argument called for in a more formal proof.

The following examples use one of these three proof techniques:

Proposition 93   Given that $${\frac{d}{dx} x =1}$$, $${\frac{d}{dx} 1 =0}$$, and the product rule

$$\frac{d}{dx} u v = u \frac{d}{dx} v + v \frac{d}{dx} u$$

we get $${\frac{d}{dx}x^n=nx^{n-1}}$$ for all $n\in \ensuremath{\mathbb{N}}$.

(4 Points )

Proposition 94   The product of n numbers may be grouped any way you please.

(4 Points )

Proposition 95   $${\sum_{k=0}^n k = \frac{n(n+1)}{2}}$$.

(4 Points )

Proposition 96   $${\sum_{k=0}^n k^2 = \frac{n(n+1)(2n+1)}{6}}$$.

(4 Points )

Proposition 97   $${\sum_{k=0}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2}$$.

(4 Points )

Proposition 98   $${\sum_{k=0}^n a^k = \frac{1-a^{k+1}}{1-a}}$$.

(4 Points )

Proposition 99   Every natural number $n>1$ is either a prime or is the product of primes.

(4 Points )

Theorem 100 (Division Algorithm)   If $m$ and $n$ are positive natural numbers, then there are natural numbers $q$ and $r$ with $0\leq r < m$ and $n=qm+r$.

(4 Points )

Theorem 101 (Euclidean Algorithm)   If $m$ and $n$ are positive natural numbers, then the greatest common divisor of $m$ and $n$ can be expressed as $an+bm$ for some integers $a$ and $b$.

(4 Points )

Corollary 102   If $n\vert pq$ and the largest common divisor of $n$ and $p$ is 1, then $n\vert q$.

(2 Points )

Corollary 103   Any natural number $n>1$ has a prime factorization which is unique up to the order of the factors.

(4 Points )