# What is Mathematical Induction?

**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.