Mathematical induction is a mathematical technique is used to prove a statement, a theorem or a formula is true for every natural number.

An essential property of the set **N **= {1, 2, 3, …} of positive integers follows:

**Principle of Mathematical Induction I: **Let P be a proposition defined on the positive integers **N**; that is, P(n) is either true or false for each n ∈ **N**. Suppose P has the following two properties:

(i) P(1) is true.

(ii) P(k + 1) is true whenever P(k) is true.

Then P is true for every positive integer n ∈ **N**.

We shall not prove this principle. In fact, this principle is usually given as one of the axioms when **N **is developed axiomatically.

**Principle of Mathematical Induction II: **Let P be a proposition defined on the positive integers **N **such that:

(i) P(1) is true.

(ii) P(k) is true whenever P(j) is true for all 1 ≤ j < k.

Then P is true for every positive integer n ∈ **N**.

**Note: **Sometimes one wants to prove that a proposition P is true for the set of integers {a, a + 1, a + 2, a + 3, . . .} where a is any integer, possibly zero. This can be done by simply replacing 1 by a in either of the above Principles of Mathematical Induction.

The technique has two steps to prove any statement-

1. Base step (it proves that a statement is true for the initial value)

2. Inductive step (it proves that is the statement is true for n’th iteration then it is also true for (n+1)’th iteration.

Example:

Sol. here for n = 1, 1 = 1²

Now let us assume that the statement is true for n = k

Hence we assume that is true.

Now we need to prove that-

So that which satisfies the second step.

Hence-

**Example-2:****Prove 1+2+…+n=n(n+1)/2 using a proof by induction**

**Sol.**

Let n=1: 1 = 1(1+1)/2 = 1(2)/2 = 1 is true,

**Step-1: **Assume n=k holds: 1+2+…+k=k(k+1)/2

Show n=k+1 holds: 1+2+…+k+(k+1)=(k+1)((k+1)+1)/2

Substitute k with k+1 in the formula to get these lines. Notice that I write out what I want to prove.

**Step-2: **Now start with the left side of the equation

1+2+…+(k+1)=1+2+…+k+(k+1)

=k(k+1)/2 + (k+1)

=(k(k+1) + 2(k+1))/2 by 2/2=1 and distribution of division over addition

=(k+2)(k+1)/2 by distribution of multiplication over addition

=(k+1)(k+2)/2 by commutativity of multiplication.

**Example-3: Prove the following by using the principle of mathematical induction for all n ****∈**** N-**

Sol. Here, n = 1, which is true

Step-1: Assume n = k holds-

Now show n = k + 1 also holds-

Consider-

Which is also true for n = k + 1.

Hence proved.