Induction Proofs

Theorem 8.1   The following 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. For example:

Proposition 8.2   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} }$.

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

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

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

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

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

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

Theorem 8.9 (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.

Theorem 8.10 (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.

Corollary 8.11   If n|pq and the largest common divisor of n and p is 1, then n|q.

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