PRINCIPLE OF MATHEMATICAL INDUCTION

Home » Principle of Mathematical Induction » PRINCIPLE OF MATHEMATICAL INDUCTION

Statement: A sentence which is either exactly true or exactly false is called a statement.

Example: “26 is divisible by 5” is a statement.

“25 is divisible by 2 and 5” is a statement.

By Principle of Mathematical Induction, we can prove a mathematical statement true or false.

If a statement satisfies the following three steps, the statement will be correct.

Step 1: To prove a statement P(n) is true for first natural number1. [P(1) is true].

Step 2: To consider the statement P(n) is true for any other natural number. [Let P(m) is true].

Step 3: To prove the statement P(n) is true for a natural number (m + 1). [To prove P(m + 1) is true]

Example 1:

Prove that P\left( n \right):\,{1^2} + {2^2} + {3^2} + ....... + {n^2} = \frac{{n\left( {n + 1} \right)\left( {2n + 1} \right)}}{6} .

Solution:

Step 1: P\left( 1 \right):\,\,\,{1^2}\, = \frac{{1\left( {1 + 1} \right)\left( {2.1 + 1} \right)}}{6}

\begin{array}{l}
\,\,\,\,\,\,\,\,\,\,\, \Rightarrow \,\,1\,\, = \,\,\frac{{2 \times 3}}{6}\\
\,\,\,\,\,\,\,\,\,\, \Rightarrow \,\,1\,\,\, = \,\,\,1
\end{array}

Step 2: Let P(m) is true.

P\left( m \right):\,\,\,{1^2} + {2^2} + {3^2} + ............ + {m^2} = \frac{{m\left( {m + 1} \right)\left( {2m + 1} \right)}}{6}\,\,\,\,\,\,\,\,.......\left( 1 \right)

Step 3: To prove P(m+1) is true.

\begin{array}{l}
P\left( {m + 1} \right):\,{1^2} + {2^2} + {3^2} + .......... + {\left( {m + 1} \right)^2} = \frac{{\left( {m + 1} \right)\left( {m + 2} \right)\left( {2m + 3} \right)}}{6}\\
{\rm{L}}{\rm{.H}}{\rm{.S }} = \,\,{1^2} + {2^2} + {3^2} + .......... + {\left( {m + 1} \right)^2}\\
\,\,\,\,\,\,\,\,\,\,\,\,\, = \,\,{1^2} + {2^2} + {3^2} + .......... + {m^2} + {\left( {m + 1} \right)^2}\\
\,\,\,\,\,\,\,\,\,\,\,\,\, = \,\frac{{m\left( {m + 1} \right)\left( {2m + 1} \right)}}{6} + {\left( {m + 1} \right)^2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left\{ {{\rm{From}}\,{\rm{equation}}\,{\rm{1}}} \right\}\\
\,\,\,\,\,\,\,\,\,\,\,\,\, = \,\left( {m + 1} \right)\left[ {\frac{{m\left( {2m + 1} \right)}}{6}\, + \left( {m + 1} \right)} \right]\\
\,\,\,\,\,\,\,\,\,\,\,\,\, = \,\left( {m + 1} \right)\left[ {\frac{{2{m^2} + m + 6m + 6}}{6}} \right]\\
\,\,\,\,\,\,\,\,\,\,\,\,\, = \,\left( {m + 1} \right)\left[ {\frac{{2{m^2} + 7m + 6}}{6}} \right]\\
\,\,\,\,\,\,\,\,\,\,\,\,\, = \,\left( {m + 1} \right)\left[ {\frac{{2{m^2} + 4m + 3m + 6}}{6}} \right]\\
\,\,\,\,\,\,\,\,\,\,\,\,\, = \,\frac{{\left( {m + 1} \right)\left( {m + 2} \right)\left( {2m + 3} \right)}}{6}
\end{array}

Example 2: Prove that:P\left( n \right):{5^{2n + 2}} - 24n - 25 is divisible by 576.

Solution:

Step 1: P\left( 1 \right) = {5^{2\left( 1 \right) + 2}} - 24\left( 1 \right) - 25

\begin{array}{l}
 = {5^4} - 24 - 25\\
 = 625 - 24 - 25\\
 = 576
\end{array}

576 is divisible by 576.

Step 2: Let P(m) is true.

P\left( m \right):{5^{2m + 2}} - 24m - 25 = 576k\,\,\,\,\,\,\,\,\,........\,\,\left( 1 \right)

Step 3: To prove: P(m+1) is true.

\begin{array}{l}
P\left( {m + 1} \right) = {5^{2\left( {m + 1} \right) + 2}} - 24\left( {m + 1} \right) - 25\,\\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \,{5^{2m + 2 + 2}} - 24m - 24 - 25\\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \,{5^{2m + 2}}{.5^2} - 24m - 49\\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \left( {576k + 24m + 25} \right)25 - 24m - 49\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,............\,\left\{ {{\rm{From}}\,\,\left( {\rm{1}} \right)} \right\}\\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \,576 \times 25k + 600m + 625 - 24m - 49\\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \,576 \times 25k + 576m + 576\\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \,576\left( {25k + m + 1} \right)\,\,{\rm{which}}\,{\rm{is}}\,{\rm{divisible}}\,{\rm{by}}\,{\rm{576}}\\
\,
\end{array}

\therefore \,\,\,\,\,P\left( {m + 1} \right)is divisible by 576.

Hence P(n) is true for n\,\, \in \,\,N

Example 3: P\left( n \right):\,{\left( {1 + x} \right)^n} \ge 1 + nx\,;\,\,n\, \in \,{Z^ + }

Solution:

Step 1: P\left( 1 \right):\,\,{\left( {1 + x} \right)^1} \ge \,1 + 1.\,x

1 + x \ge 1 + x

\therefore P\left( 1 \right)is true.

Step 2: Let P(m) is true.

{\left( {1 + x} \right)^m} \ge 1 + mx\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,.........\,\,\left( 1 \right)

Step 3: To prove P(m+1) is true.

{\left( {1 + x} \right)^{m + 1}} \ge 1 + \left( {m + 1} \right)x\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,..........\,\,\left( 2 \right)

From equation (1)

{\left( {1 + x} \right)^m} \ge 1 + mx

Multiplying both sides by \left( {1 + x} \right)

\begin{array}{l}
 \Rightarrow \,{\left( {1 + x} \right)^m}\left( {1 + x} \right) \ge \left( {1 + mx} \right)\left( {1 + x} \right)\\
 \Rightarrow \,{\left( {1 + x} \right)^{m + 1}} \ge \,1 + mx + x + m{x^2}\\
 \Rightarrow \,{\left( {1 + x} \right)^{m + 1}} \ge 1 + \left( {m + 1} \right)x + m{x^2}\\
\therefore \,\,\,m{x^2} \ge 0\\
\therefore \,\,\,{\left( {1 + mx} \right)^{m + 1}} \ge 1 + \left( {m + 1} \right)x
\end{array}

\therefore P\left( {m + 1} \right) is true.

Here, P(n) is true for n\, \in \,{Z^ + }.

Posted on