Mathematical induction is a method to prove that some statement
about the integer n is true for all n. In this method, first we prove the statement
when n has its smallest value, say p0. This is called the base case or basis or trivial case.

Then we prove the statement for k > p0, assuming that it has already been proved for all values between p0 and k, i.e We will assume that P(k) holds true. With that assumption we will prove the case for P(k+1) . This is called the induction. Please see the above picture diagram for general idea about mathematical induction. This kind proof is ideal for recurrences.

Principle of Mathematical Induction

The principle of mathematical induction is usually described in two forms. The one we have talked about is called the weak form.

If the statement p(base) holds true, and the statement P(k) ⇒ P(k+1) holds true for all k > base, then

P(n) is true for all integers n ≥ base.

Strong form:

If the statement p(base) holds true, and the statement

P(base)∧ P(b+1) ∧ … P(k)⇒ P(k+1)) holds true for all k > base, then

P(n) is true for all integers n ≥ base.