Induction is the process of inferring a general statement from the truth of particular cases.
For example, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 7 + 3 and so on. From these cases, you may make a general statement "every even integer except 2 can be expressed as a sum of two prime numbers."
There are hundreds of particular cases where this is known to be true. But you cannot conclude that this statement is true unless it is proved. Such a statement inferred from particular cases is called a conjecture. A conjecture remains a conjecture until it is proved or disproved.
Let the conjecture be a statement involving natural numbers. Then a method to prove a general statement after it is known to be true in some particular cases is the principle of mathematical induction.
Mathematical induction is a principle by which one can conclude that a statement is true for all positive integers, after proving certain related propositions.
Principle of Mathematical Induction
Corresponding to each positive integer n, let there be a statement or proposition P(n).
If P(1) is true and P(k+1) is true whenever P(k) is true, then P(n) is true for all positive integers n.
- Show that the result is true for n = 1.
- Assume the validity of the result for n equal to some arbitrary but fixed natural number, say k.
- Show that the result is also true for n = k + 1.
- Conclude that the result holds for all natural numbers.