## Introduction

Mathematical Induction is a methodology for proving natural-number conclusions, a formula or existing theorems.

There are 2 steps involved in order to prove these statements using Induction:

**Step 1(Base step) :**

Consider a starting point for the assertion to be true. It will always be true must prove that the statement is correct when n = starting value.

*Mathematically*:

Let n_{0} be a fixed integer. Suppose T (n) is a statement involving the natural number n, and we wish to prove that P (n) is valid for all n ≥ n_{0}.

T (n_{0}) is true i.e. T (n) is true for n = n_{0}.

**Step 2(Induction Step) :**

Assuming the statement to be **true** for any value of *n = k*. Then prove that the statement is true for *n = k+1*.

__Mathematically__:

Let n_{0} be a fixed integer. Suppose T (n) is a statement involving the natural number n and we wish to prove that P (n) is true for all N ≥ n_{0}.

Assume that the P (k) is true for n = k.

Then P (K+1) should also be true.

## Examples

**Use the Principle of Mathematical Induction to verify that, for n any positive integer, 6n-1 is divisible by 5.**

Solution:

For any n ≥ 1, let P_{n} be the statement that 6^{n} − 1 is divisible by 5.__Base Case:__ The statement P_{1} says that

6^{ 1} − 1 = 6 − 1 = 5 *Eq No. 1*

is divisible by 5, which is true. __Inductive Step:__ Fix k ≥ 1, and suppose that P_{k} holds, that is, 6^{k}_{ }− 1 is divisible by 5.

It remains to show that P_{k}+1 holds, that is, that 6^{k+1} − 1 is divisible by 5.

6^{ k+1} − 1 = 6(6^{k} ) − 1

= 6(6^{k} − 1) − 1 + 6 *From Eq. No-1*

= 6(6^{k} − 1) + 5

By P_{k}, the first term 6(6^{k} − 1) is divisible by 5, the second term is divisible by 5.

Therefore the left-hand side is also divisible by 5.

Therefore P^{k+1} holds.

Thus, P(n) holds true by the principle of mathematical Induction, for all n ≥ 1.

**2. Verify the following mathematical equation using Mathematical Induction:****1 + 3 + 5 + ··· + 2n − 1 = n ^{2}**

^{ }

Solution:

__Base Step:__ We are going to prove P(1).

LHS of P(1) = 1

= 1^{2}

= RHS of P(1).

So P(1) is true.__Inductive Step:__ Now, we’ll prove that for any natural number k, “if P(k) is true then P(k +1) is true.” So assume P(k) is true, i.e.

1+3+5+ ··· + 2k − 1 = k^{2}

Therefore for P(k + 1):

LHS of P(k + 1) = 1 + 3 + 5 + ··· + 2k − 1 + 2(k + 1) − 1

= (LHS of P(k)) + 2(k + 1) − 1

= (RHS of P(k)) + 2k + 1 *(by inductive assumption)*

= k^{2 }+ 2k +1

= (k + 1)^{2}

= RHS of P(k + 1)

So P(k + 1) is true, if P(k) is true.

Hence, by induction P(n) is true for all natural numbers