# Mathematical Induction - Discrete Mathematics

## What is Mathematical Induction?

The technique that is used for proving the results or for natural numbers, the statements are established is known as mathematical induction.

### Definition of Mathematical Induction

A mathematical technique used for proving a statement, formula or a theorem is true for every natural number is known as Mathematical Induction. A statement can be proved in two steps:

Step 1(Base step) – The statement is proved to be true for the initial value.

Step 2(Inductive step) – The statement is proved to be true for the nth iteration.

## How to Do?

Step 1 – An initial value for which the statement is true is considered. It is represented as n = initial value.

Step 2 – It is assumed that the statement is true for any value of n = k. Then the statement is proved true for n = k+1. Here n = k+1 is broken down into two parts, one part is n = k , which is the proved one and the second part is proved.

### Problem 1

is a multiple of 2 for n = 1, 2, ...

### Solution

Step 1 − For which is a multiple of 2

Step 2 – It is assumed that3n−1 is true for n=k and hence, 3k−1 is true.

It is to be proved that

1 is also a multiple of 2

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

Hence,

Hence it is proved that3n–1 is a multiple of 2.

### Solution

Step 1 − For , Hence, step 1 is satisfied.

Step 2 – It is assumed that the statement is true for n=k.

### Problem 3

For every natural number n, prove thatis true.

### Solution

Step 1 − ForHence, step 1 is satisfied.

## What is Strong Induction?

One more form of mathematical induction is Strong Induction. This induction proves that a propositional function P(n) is true for all the positive integers , by using the following steps:

• Step 1(Base step) – Step 1 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.