Suppose we have an assertion P(n) about the integers.
Then if we show both of (i) and (ii) below, then P(n) is true for all n >= m.
(i). P(m) is true
(ii). For each k >= m, If P(k) is true, then P(k+1) is true.
Examples
I. The Fibonacci Numbers
The Fibonacci numbers are defined by the recurrence relation,
So the first few Fibonacci Numbers are:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,...
There are numerous curious properties of the Fibonacci Numbers. Once guessed, most such properties can be verified by induction. Here are a few examples.
1. For every n >= 1, 
.
2. For every n >= 1, 
3. More generally, For every k >= 1, and n >= 1, if 
.
4. For every n >= 1 and m >= 1, 
.
5. For every n >= 1, 
.
6. For n >= 2, 
.
Another form of Mathematical Induction is the so-called Strong Induction described below.
Principle of Strong Induction
Suppose that P(n) is a statement about the positive integers and
(i). P(1) is true, and
(ii). For each k >= 1, if P(m) is true for all m < k, then P(k) is true.
Then P(n) is true for all integers n >= 1.
We will see examples of this form of induction later in the course.
Also equivalent to the Principle of Induction is the Well-Ordering Principle.
The Well-Ordering Principle simply states that every non-empty subset of the positive integers has a smallest element. This simple observation can serve as the foundation of some very significant mathematical arguments.
Definition. Let n and m be positive integers, and let
A(n,m) = { an + bm >0 : a and b are integers }.
(So, z belongs to A(n, m) if and only if z is an integer, z > 0, and there exists integers a and b such that z = an + bm.)
Theorem. For any positive integers n and m, the smallest element of A(n, m) is gcd(m, n) - the greatest common divisor of n and m.
Proof. By the Well-ordering Principle, A(n, m) does have a smallest element. Let d denote the smallest element of A(n, m). Then d = an + bm for some integers a and b. We will first show that d is a common divisor of m and n. By the divison algorithm, there exist integers q and r with 0 <= r < d and n = qd + r. But then,
r = n - qd = n - q(an + bm) = (qa+1)n - (qb)m.
So if r >0, then r must belong to A(n, m). However, this is impossible since r < d and d is the smallest element of A(n, m). So it must be that r = 0. Hence, n = qd and this means that d divides n. Similarly, d divides m. So we have shown that d is a common divisor of n and m. On the other hand if t is any common divisor of m and n then say n = kt and m = st, then d = an + bm = akt + bst = (ak+bs)t. So d is a multiple of t. Hence d is at least as large as any other common divisor of m and n. Thus d is the largest of the common divisors of n and m. This completes the proof.
Corollary. If n and m are relatively prime, then there exist integers a and b
such that an + bm = 1.
The following simple lemma is often useful. (Its proof is an exercise for you).
Lemma. If n and m are relatively prime, then so are n and n + m, and so are n and n - m.
Exercise: (Let fn denote the nth Fibonacci number.)
1. Show that for each n >= 1, fn and fn+1 are relatively prime.
2. Prove or Disprove: For each n >= 1, fn and fn+2 are relatively prime.
3. Prove or Disprove: For each n >= 1, fn and fn+3 are relatively prime.