Chapter 1: Complete Induction

Sometimes, I cannot understand the meaning of Complete Induction.  I always confuse how to use it. I have an example here which gets from “How to prove it”.

Sample: Suppose n is an integer larger than 1 and n is prime. Then P(n): 2^n -1 is prime.

We can see

n = 2, 2^n – 1 = 3

n = 3, 2^n – 1 = 7

n = 5, 2^n – 1 = 31

Then, the next prime number 7 is in N. The expression holds for every prime number less than 7. So, from complete induction, P(7)  holds. Similarly, the expression holds too for next prime number 11. Such that, I get conclusion that P(n) holds for every prime number. As a matter of fact, everyone knows this predict is not correct. But I cannot figure out where is wrong with my proof.

The definition of Complete Induction is described for all natural numbers. In this sample, I do not use 4 and 6 in the proof because they are not prime number. Does this not obey the rule of Complete Induction? I do not think so.  At ton of proofs, we define the base case which is from bigger numbers than 1. That means the domain of variable may not include all natural numbers.