Mathematical Induction – Concept & Examples

Theory of Mathematical induction is one of the method to prove mathematical statements, formulas and expressions.
For example, If you want to check if the below expression is right or wrong, you can do it with the help of the principal of mathematical induction

1+2+3+4+5+6+7+\quad .\quad .\quad .\quad .n\quad =\frac { n(n+1) }{ 2 }

In this technique, we first check the expression with the initial value (n= initial value), then prove that if the statement is true for n = k value then it will be also be true for n= k+1 value.

Steps for mathematical Induction

Here are the exact steps you have to follow in order to prove any math formula or expression
Step 01: Check statement is True for First Case (n = 1)
Step 02: Assume statement is True for (n = k),
Step 03: then check the if the statement if True for (n = k+1)

The above three are the basic steps are absolutely necessary. Hence please try to practice the steps so that you can easily follow in your examination

Mathematical Induction Practical Example

One common example which is used to explain theory of mathematical induction is called Domino Effect.

Domino effect is the process in which the fall of one domino leads to the fall of the next domino and the process goes on and on.

We can use the above mentioned steps of mathematical induction to prove domino effect
1. Check if the first domino falls (True)
2. Assume that the domino number n is also falling
3. Check if the fall of one domino (n = k) leads to the fall of next domino (n = k+1) [True]

Hence proved that domino effect will lead to fall of all the involving dominos.
I hope now you have basic idea of the principal of mathematical induction process. Let’s see some example on the mathematical expression to understand the concept better.

Mathematical Induction Solved Problems

Example 01
{ 1 }^{ 2 }+2^{ 2 }+{ 3 }^{ 2 }+{ 4 }^{ 2 }+{ 5 }^{ 2 }+.\quad .\quad .\quad .+{ n }^{ 2 }=\frac { n(n+1)(2n+1) }{ 6 }

Solution
We can easily prove this formula by using all the three steps mentioned above.

Step 01
Checking the expression for its initial value (n = 1)
\ { 1 }^{ 2 }=\frac { 1\times 2\times 3 }{ 6 } \\\ \\ 1=1

we can see that L.H.S = R.H.S, so step 1 is clear

Step 02
Assuming that the above expression is correct for n = k
{ 1 }^{ 2 }+2^{ 2 }+{ 3 }^{ 2 }+{ 4 }^{ 2 }+{ 5 }^{ 2 }+.\quad .\quad .\quad .+{ k }^{ 2 }=\frac { k(k+1)(2k+1) }{ 6 } ——– eq (1)

Step 03
If n = k is True, then n = k+1 should also be true
{ 1 }^{ 2 }+2^{ 2 }+{ 3 }^{ 2 }+{ 4 }^{ 2 }+{ 5 }^{ 2 }+.\quad .\quad .\quad .+{ k }^{ 2 }+(k+1)^{ 2 }=\frac { (k+1)(k+2)(2k+3) }{ 6 }

we have to prove that L.H.S = R.H.S

Using the equation (1), we can write the above equation as:

\frac { (k)(k+1)(2k+1) }{ 6 } +(k+1)^{ 2 }=\frac { (k+1)(k+2)(2k+3) }{ 6 } \\\ \\ \\\ \\ \frac { (k)(k+1)(2k+1)+6(k+1)^{ 2 } }{ 6 } =\frac { (k+1)(k+2)(2k+3) }{ 6 } \\\ \\ \\\ \\ \frac { (k+1) (2k^{ 2 }+7k+6) }{ 6 } =\frac { (k+1)(k+2)(2k+3) }{ 6 } \\\ \\ \\\ \\ \frac { (k+1)(k+2)(2k+3) }{ 6 } =\frac { (k+1)(k+2)(2k+3) }{ 6 }

L.H.S = R.H.S
This means that by the principle of mathematical induction, the above expression is correct

Example 02
Prove the following using the principle of Mathematical Induction
1 + 3 + 5 + 7 + 9 + . . . . .+ ( 2n – 1) = n²

Solution
Using the above mentioned steps, we will solve this question

Step 01
Check if the statement is correct for n = 1
==> 1 = 1²
==> 1 = 1
L.H.S = R.H.S


Step 02
Assume that the statement is correct for n = k
1 + 3 + 5 + 7 + 9 + . . . . .+ ( 2k – 1) = k² —–eq(1)

Step 03
Check if the statement is correct for n = k + 1
1 + 3 + 5 + 7 + 9 + . . . . . + ( 2k – 1) + [2(k+1) – 1] = (k+1)²

Using eq(1) for the above expression, we can write:
==> k² + [2(k+1) – 1] = (k+1)²
==> k² + 2k+1 = (k+1)²
==> (k+1)² = (k+1)²
Hence L.H.S = R.H.S
Thus with the help of mathematical induction we proved that the above statement is correct

Example 03
Prove the following principle using the concept of mathematical induction
1.2.3 + 2.3.4 +3. 4. 5 + . . . . . . .+ n(n+1) (n+2) = (n) (n+1) (n+2) (n+3)/4

Solution
We have to do the same above mentioned steps to prove the expression

Step 1
Putting the value n = 1 in the above expression we get,
==> 1 .2 .3 = (1 * 2 * 3 * 4)/4
==> 1 .2 .3 = 1 * 2 * 3
We can see that L.H.S = R.H.S
Hence the statement is true for n = 1, now let’s move on to step 2

Step 02
Assuming n = k is also true
1.2.3 + 2.3.4 +3. 4. 5 + . . . . . . .+ k(k+1) (k+2) = \frac { (k+1)(k+2)(k+3)(k+4) }{ 4 } –eq(1)

Step 03
Putting n = k+1 and check if L.H.S = R.H.S

1.2.3 + 2.3.4 +3. 4. 5 + . . . . . . .+ k(k+1) (k+2) + (k+1) (k+2) (k+3) = \frac { (k+1)(k+2)(k+3)(k+4) }{ 4 }

Using the eq(1), the above expression can be written as:

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

you can see that L.H.S = R.H.S
Hence the expression holds true through the principle of mathematical induction

Example 04
Prove the following expression using mathematical expression
{ 1 }^{ 2 }{ +2 }^{ 2 }+3^{ 2 }+{ 4 }^{ 2 }{ +5 }^{ 2 }+.\quad .\quad .\quad .+n^{ 2 }>\frac { { n }^{ 3 } }{ 3 }

Solution
Step 1
Checking the expression for initial value (n=1), we get
{ 1 }^{ 2 }>\frac { { 1 }^{ 3 } }{ 3 } \\\ \\ 1>\frac { 1 }{ 3 }

L.H.S > R.H.S
The condition is satisfied, let’s move on to the next step

Step 02
Assuming that the expression is true for n=k
we get the following expression
{ 1 }^{ 2 }{ +2 }^{ 2 }+3^{ 2 }+{ 4 }^{ 2 }{ +5 }^{ 2 }+.\quad .\quad .\quad .+k^{ 2 }>\frac { { k }^{ 3 } }{ 3 } —–eq(1)

Step 03
if n=k is true, then n=k+1 will also be true

{ 1 }^{ 2 }{ +2 }^{ 2 }+3^{ 2 }+{ 4 }^{ 2 }{ +5 }^{ 2 }+.\quad .\quad .\quad .+k^{ 2 }+\quad { (k+1) }^{ 2 }\quad >\frac { { (k }+1)^{ 3 } }{ 3 } \\\ \\ using\quad equation\quad (1),\quad we\quad can\quad write\\\ \\ \\\ \\ \frac { { k }^{ 3 } }{ 3 } +\quad { (k+1) }^{ 2 }\quad >\frac { { (k }+1)^{ 3 } }{ 3 } \\\ \\ \\\ \\ \frac { { k }^{ 3 }+3{ k }^{ 2 }+3+6k }{ 3 } >\frac { { (k }+1)^{ 3 } }{ 3 } \\\ \\ \\\ \\ \frac { ({ k }+1)^{ 3 }+3k+2 }{ 3 } >\frac { { (k }+1)^{ 3 } }{ 3 } \

Hence L.H.S > R.H.S
This means that the above expression is valid