# Mathematical Induction

Mathematical induction (or weak mathematical induction) is a method to prove or establish mathematical statements, propositions, theorems, or formulas for all natural numbers ‘n ≥1.’

## Principle

It involves two steps:

1. Base Step: It proves whether a statement is true for the initial value (n), usually the smallest natural number in consideration.
2. Inductive Step: It proves that when the statement is true for the natural number (n) (or nth iteration), it must also be true for the next number (n + 1) or (n+1)th iteration.

Here, we will discuss this method with an example.

## Proof

Let us consider the statement:

For all natural numbers up to n, 12 + 22 + 32 + … + n2 = ${\dfrac{n\left( n+1\right) \left( 2n+1\right) }{6}}$

For the initial value, n = 1, 12 = 1 = ${\dfrac{1\left( 1+1\right) \left( 2\times 1+1\right) }{6}}$, which is true.

Assuming the statement is also true for n = k, we get

12 + 22 + … + k2 =  ${\dfrac{k\left( k+1\right) \left( 2k+1\right) }{6}}$

Here, we have to prove the given statement for n = k + 1,

12 + 22 + 32 + … + (k + 1)2

= 12 + 22 + 32 + … + k2 + (k + 1)2

= {12 + 22 + 32 + … + k2} + (k + 1)2

= ${\dfrac{k\left( k+1\right) \left( 2k+1\right) }{6}}$ + ${\left( k+1\right) ^{2}}$

= ${\dfrac{k\left( k+1\right) \left( 2k+1\right) +6\left( k+1\right) ^{2}}{6}}$

= ${\dfrac{\left( k+1\right) \left[ k\left( 2k+1\right) +6\left( k+1\right) \right] }{6}}$

= ${\dfrac{\left( k+1\right) \left( 2k^{2}+7k+6\right) }{6}}$

= ${\dfrac{\left( k+1\right) \left( k+2\right) \left( 2k+3\right) }{6}}$

= ${\dfrac{\left( k+1\right) \left[ \left( k+1\right) +1\right] \left[ 2\left( k+1\right) +1\right] }{6}}$, which proves that the given statement is true for n = k + 1.

Thus, 12 + 22 + 32 + … + n2 = ${\dfrac{n\left( n+1\right) \left( 2n+1\right) }{6}}$, is true for all natural numbers n.

Hence, the method of mathematical induction proves the given statement: For all natural numbers up to n, 12 + 22 + 32 + … + n2 = ${\dfrac{n\left( n+1\right) \left( 2n+1\right) }{6}}$

## Solved Examples

Using Mathematical Induction, prove the given statement: For any natural number n, 22n – 1 is divisible by 3.

Solution:

Considering n = 1, we get,
22(1) – 1 = 22 – 1 = 4 – 1 = 3, divisible by 3
Thus, the given statement is true for n = 1.
Assuming n = k, the statement 22k – 1 is divisible by 3
It means 22k – 1 = 3p, where p is a natural number.
Now, considering n = k + 1, we get
22(k + 1) – 1
= 22k + 2 – 1
= (22k × 22) – 1
= 4(22k) – 1
= (22k – 1) + 3(22k)
= 3p + 3(22k)
=3(p + 22k), divisible by 3, which proves that the given statement is true for n = k + 1
Thus, 22n – 1 is divisible by 3 for any natural number ‘n.’

Prove that (xy)n = xnyn is true for every natural number n using mathematical induction.

Solution:

Considering n = 1, we get the given statement (xy)1 = xy = x1y1, true
Assuming n = k, the statement (xy)k = xkyk is true.
Now, considering n = k + 1, we get
(xy)k + 1
= (xy)(xy)k
= (xy)(xkyk)
= (xkx)(yky)
= xk + 1yk + 1, which proves that the given statement is true for n = k + 1
Thus, (xy)n = xnyn is true for every natural number ‘n.’

Use induction to prove that 1 + 2 + 3 + … + n = ${\dfrac{n\left( n+1\right) }{2}}$, where n is any natural number.

Solution:

Considering n = 1, we get the statement 1 = 1, which is true.
Assuming n = k, the statement can be written as 1 + 2 + 3 + … + k = ${\dfrac{k\left( k+1\right) }{2}}$ is true.
Now, considering n = k + 1, we get
1 + 2 + 3 + … + (k + 1)
= 1 + 2 + 3 + … + k + (k + 1)
= ${\dfrac{k\left( k+1\right) }{2}+\left( k+1\right)}$
= ${\dfrac{k\left( k+1\right) +2\left( k+1\right) }{2}}$
= ${\dfrac{\left( k+1\right) \left( k+2\right) }{2}}$
= ${\dfrac{\left( k+1\right) \left[ \left( k+1\right) +1\right] }{2}}$, which proves that the given statement is true for n = k + 1
Thus, 1 + 2 + 3 + … + n = ${\dfrac{n\left( n+1\right) }{2}}$, where n is any natural number.