# Mathematical Induction

**Mathematical induction**, is a technique for proving results or establishing statements for natural numbers. This part illustrates the method through a variety of examples.

## Definition

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

The technique involves *two* steps to prove a statement, as stated below −

**Step 1(Base step)** − It proves that a statement is true for the initial value.

**Step 2(Inductive step)** − It proves that if the statement is true for the n^{th} iteration (or number *n*), then it is also true for (n+1)^{th}iteration ( or number *n+1*).

## How to Do It

**Step 1** − Consider an initial value for which the statement is true. It is to be shown that the statement is true for n = initial value.

**Step 2** − Assume the statement is true for any value of *n = k*. Then prove the statement is true for *n = k+1*. We actually break*n = k+1* into two parts, one part is n = k (which is already proved) and try to prove the other part.

### Problem 1

3^{n}−1 is a multiple of 2 for n = 1, 2, …

**Solution**

Step 1 − For n = 1, 3^{1}−1 = 3−1 = 2 which is a multiple of 2

Step 2 − Let us assume 3^{n}−1 is true for n = k, Hence, 3^{k} −1 is true (It is an assumption)

We have to prove that 3^{k+1}−1 is also a multiple of 2

3^{k+1} − 1 = 3 × 3^{k} − 1 = (2 × 3^{k}) + (3^{k} −1)

The first part (2 × 3^{k}) is certain to be a multiple of 2 and the second part (3^{k} −1) is also true as our previous assumption.

Hence, 3^{k+1} − 1 is a multiple of 2.

So, it is proved that 3^{n} − 1 is a multiple of 2.

### Problem 2

1 + 3 + 5 + … + (2n−1) = n^{2} for n = 1, 2, …

**Solution**

Step 1 − For n = 1, 1 = 1^{2}, Hence, step 1 is satisfied.

Step 2 − Let us assume the statement is true for n = k.

Hence, 1 + 3 + 5 + … + (2k−1) = k^{2} is true (It is an assumption)

We have to prove that 1 + 3 + 5 + … + (2(k+1)−1) = (k+1)^{2}also holds

1 + 3 + 5 + … + (2(k+1) − 1)

= 1 + 3 + 5 + … + (2k+2 − 1)

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

= 1 + 3 + 5 + … + (2k − 1) + (2k + 1)

= k^{2} + (2k + 1)

= (k + 1)^{2}

So, 1 + 3 + 5 + … + (2(k+1) − 1) = (k+1)^{2} hold which satisfies the step 2.

Hence, 1 + 3 + 5 + … + (2n − 1) = n^{2} is proved.

### Problem 3

Prove that (ab)^{n} = a^{n}b^{n} is true for every natural number *n*

**Solution**

Step 1 − For n = 1, (ab)^{1} = a^{1}b^{1} = ab, Hence, step 1 is satisfied.

Step 2 − Let us assume the statement is true for n = k, Hence, (ab)^{k} = a^{k}b^{k} is true (It is an assumption).

We have to prove that (ab)^{k+1} = a^{k+1}b^{k+1} also hold

Given, (ab)^{k} = a^{k}b^{k}

Or, (ab)^{k}(ab) = (a^{k}b^{k}) (ab) [Multiplying both side by ‘ab’]

Or, (ab)^{k+1} = (aa^{k}) ( bb^{k})

Or, (ab)^{k+1} = (a^{k+1}b^{k+1})

Hence, step 2 is proved.

So, (ab)^{n} = a^{n}b^{n} is true for every natural number n.

## Strong Induction

Strong Induction is another form of mathematical induction. Through this induction technique, we can prove that a propositional function, *P(n)* is true for all positive integers, *n*, using the following steps −

**Step 1(Base step)**− It proves that the initial proposition*P(1)*true.**Step 2(Inductive step)**− It proves that the conditional statement [p(1) ∧ p(2) ∧ p(3) ∧…………∧ p(k)] → p(k + 1) is true for positive integers k.