Ordinary Induction Vs Complete Induction.

In math, the most frequently used induction proof is ordinary induction, but sometimes, complete induction requires stronger criteria,and thus more convincing. However, It is also proved that those two induction method can prove each other.

• Ordinary Induction 

1. Structure: 

Let n be any number in Z+, p(n) be a statement satisfying the following two conditions.
(1) p(1) is true;
(2) For any k in Z+, p(k) is true then p(k+1) is true.

Then p(n) is true for all k in Z+.
 
   2.  An example of ordinary induction:

Question:Let P(n) be the statement "Postage of n cents (n>=12) can be formed using 4-cent and 5-cent stamps".

Proof:Base case: k = 12

P(12) is true, because 12 cents can be formed using three 4-cent stamps.

Induction:

Assume that P(k) is true, that is, that postage of k cents can be formed using some combination of 4-cent and 5-cent stamps.

Then to form postage of k + 1 cents, there are two possibilities.

1) If any 4-cent stamps were used to get k cents of postage, take one of the 4-cent stamps and replace it with a 5-cent stamp. You now have k + 1 cents of postage.

2) If only 5-cent stamps were used to get k cents of postage, since we know that k ≥ 12, we have at LEAST three 5-cent stamps. (I.e. the smallest k that can only be formed using 5-cent stamps is 15.) So if you replace any three 5-cent stamps with four 4-cent stamps, you will have k + 1 cents of postage.

• Complete Induction:

1. Structure:

Let n be any number in Z+, p(n) be a statement satisfying the following two conditions.(1) p(1) is true;
(2) For any k in Z+, (p(1)^p(2)^...^p(k)) is true, then p(k+1) is true.
Then for k in Z+, p(n) is true.

   2. An example of complete induction.
Same problem using complete induction:
Question:Let P(n) be the statement "Postage of n cents (n>=12)can be formed using 4-cent and 5-cent stamps".

Proof: Note that in order to show that p(n) is true for any n>=12 in N using complete induction, we need to show it's true for all the base case and also true for for n in N that 12<=n<=K, and then p(K+1) is also true. Then p(n) is true for any n>=12 in N.

Base case:

This proof requires 4 basis cases.

k = 12: 12 cents of postage can be formed using three 4-cent stamps.

k = 13: 13 cents of postage can be formed using two 4-cent stamps and a 5-cent stamp.

k = 14: 14 cents of postage can be formed using a 4-cent stamp and two 5-cent stamps.

k = 15: 15 cents of postage can be formed using three 5-cent stamps.

Induction:

For k > 15, assume that we can can form postages of j cents, for every j between 12 and k, inclusive (12 ≤ j ≤ k). Then, to form a postage for k + 1 cents, use the same postage as for k - 3 cents, but add a 4-cent stamp. Then for any j (12 ≤ j ≤ k), p(j) is true, then p(j+1) is also true. Then p(n) is true for any n>=12 in N.