# Principle of Mathematical Induction

What is Induction in math?

Mathematical induction is a special method or technique to prove the statements given in consideration. Generally, it is used to prove the statements of the set of natural numbers.Principle of Mathematical Induction:

Mathematical induction is used to prove that the given statement is true or not. It uses 2 steps to prove it.

First Principle of Mathematical Induction:

Base Case: The given statement is correct for first natural number that is, for n = 1, p (1) is true.

Inductive Step: If the given statement is true for any natural number like n = k then it will be correct for n = k + 1 also that is, if p (k) is true then p (k + 1) will also be true.The first principle of mathematical induction says that if both the above steps are proven then p (n) is true for all natural numbers.

Second Principle of Mathematical Induction: It is more powerful than the first principle. It is sometimes called as strong induction. It doesn’t need a base case in special case otherwise it may require to show with more than one base case. In the recursive step to prove that k + 1 is true, first we need to prove that the statement is correct for all the numbers less than k + 1 also.

First Principle of Mathematical Induction:

The mathematical induction can be proved in four steps:

1.Step: Show p (1) is true. Let n = 1 and solve.

2.Step: (Induction Hypothesis) Assume p (k) is true. Let n = k and solve.

3.step: (Induction) Show if p (k) is true then p (k + 1) is also true. Let n = k + 1 and solve.

Write the proof that p (n) is true.

Example: Prove that for any natural number n, the sum of n natural numbers is $$\frac{n(n+1)}{2}$$

Solution: Given the statement which we need to prove

$$1+2+3+……………..+n=\frac{n(n+1)}{2}$$

Step 1: Base Step

Show the statement holds for n = 1

$$1=\frac{1(1+1)}{2}=\frac{2}{2}=1$$

As the LHS = RHS

This shows that p (1) is true.

Step 2: Inductive Step

Show if p (k) is right then p (k + 1) is also right.

Assume p (k) is right

Let n = k

$$1+2+3+……………+k=\frac{k(k+1)}{2}$$

Now we have to prove that it is true for the next number also i.e. k + 1

Let n = k + 1

$$1+2+3+……………+k=\frac{((k+1)(k+1+1))}{2}$$

Using the induction hypothesis which assumes that p (k) is true, we can rewrite it as:

$$1+2+3+………………+k+k+1=k\frac{(k+1)}{2}+k+1$$ (by adding k + 1 two sides)

= $$\frac{(k(k+1)+2(k+1))}{2}$$

= $$\frac{((k+1)(k+2))}{2}$$

= $$\frac{((k+1)(k+1+1))}{2}$$

This shows that p (k + 1) is true.

The principle of mathematical induction shows that if both the above steps are true then p (n) is true for all n natural numbers.