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:
- Base Step: It proves whether a statement is true for the initial value (n), usually the smallest natural number in consideration.
- 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.
