How to prove using the Principle of Mathematical Induction?

MATHEMATICAL INDUCTION

The principle of mathematical induction has a very special place in mathematics because of its simplicity and vast amount of applications

PROGRESSIONS

Progression is a function f:N\to Ris called a sequence of real numbers denoted by \left\{ f\left( n \right) \right\}=\left\{ f\left( 1 \right),f\left( 2 \right),.....,f\left( n \right),... \right\}where f\left( n \right)is called the nth term of the sequence.  A sequence may also be denoted by \left\{ {{a}_{n}} \right\}\,or\left\{ {{u}_{n}} \right\}where a_n or u_n is the nth term of the sequence.

SERIES

If \left\{ {{u}_{n}} \right\}is a sequence then \sum{{{u}_{n}}={{u}_{1}}+}{{u}_{2}}+....+{{u}_{n}}+.... is called a series which may be finite or infinite according as the number of terns in it is finite or infinite.

ARITHMETIC PROGRESSION (A.P.)

A sequence of the form a,\,a+d,\,a+2d,.....,a+\left( n-1 \right)d,....is called an Arithmetic Progression (A.P.), whose first term is ‘a’, common difference is ‘d’ and nth term denoted by {{t}_{n}}=a+\left( n-1 \right)d.

If S_n denotes the sum of the first n terms of the above arithmetic progression, then

\[{{S}_{n}}=a+\,\left( a+d \right),+\left( a+2d \right)+…..+\left\{ a+\left( n-1 \right)d \right\}\]

\[\therefore \,{{S}_{n}}=\frac{n}{2}\left\{ 2a+\left( n-1 \right)d \right\}\]

To learn more about arithmetic progression please read the post – Arithmetic Progression

GEOMETRIC PROGRESSION (G.P.)

A sequence of the form a,\,ar,\,a{{r}^{2}},\,.....,\,a{{r}^{n-1}},....\,is called a Geometric Progression (G.P.), whose first term is ‘a’, common ratio is ‘r’ and the nth term {{t}_{n}}=a{{r}^{n-1}}.

If S_n denotes the sum of the first n terms of the above geometric progression, then

\[\therefore \,{{S}_{n}}=\frac{a\left( 1-{{r}^{n}} \right)}{1-r}\,or\,\frac{a\left( {{r}^{n}}-1 \right)}{r-1},\,r\ne 1\]

To learn more about geometric progression please read the post – Geometric Progression

HARMONIC PROGRESSION (H.P.)

A sequence of the form \frac{1}{a},\frac{1}{a+d},\frac{1}{a+2d},....,\frac{1}{a+\left( n-1 \right)d},....\,is called Harmonic Progression (H.P.), whose nth term {{t}_{n}}=\frac{1}{a+\left( n-1 \right)d}.

PRINCIPLE OF MATHEMATICAL INDUCTION

Mathematical induction is the process of proving a general theorem or formula involving the positive integer ‘n’ from particular cases.<br>A proof by mathematical induction consists of the following three steps:
(1) Show by actual substitution that the theorem is true for n = 1 or initial value.
(2) Assume the theorem is true for n = m, where ‘m’ is any integer greater than the initial value.
(3) Assuming the theorem to be true for n = m, prove that it is also true for n = m + 1.

Example 01

Q. Prove by mathematical induction that the sum of the first n natural number is \frac{n\left( n+1 \right)}{2}.

Solution:

We have prove that,

\[1+2+3+….+n=\frac{n\left( n+1 \right)}{2}\]

Step 1: For n = 1, left side = 1 and right side = \frac{1\left( 1+1 \right)}{2}=1. Hence the statement is true for n = 1.

Step 2: Now we assume that the statement to be true for n = m, then

\[1+2+3+….+m=\frac{m\left( m+1 \right)}{2}\]

Step 3: We now show that the above statement is true for n = m + 1. Adding the (m + 1)th term i.e., (m + 1) to both sides we obtain.

\[1+2+3+….+m+\left( m+1 \right)=\frac{m\left( m+1 \right)}{2}+\left( m+1 \right)\]

\[\Rightarrow 1+2+3+….+m+\left( m+1 \right)=\left( m+1 \right)\left\{ \frac{m}{2}+1 \right\}\]

\[\Rightarrow 1+2+3+….+m+\left( m+1 \right)=\left( m+1 \right)\left\{ \frac{m+2}{2} \right\}\]

\[\therefore 1+2+3+….+m+\left( m+1 \right)=\frac{\left( m+1 \right)\left( \overline{m+1}+1 \right)}{2}\]

Which is the same as the given statement for n = m + 1.
Hence by mathematical induction, the statement is true for all +ve integral values of n.

Example 02

Q. Prove by mathematical induction that,

\[{{1}^{2}}+{{2}^{2}}+{{3}^{2}}+….+{{n}^{2}}=\frac{n\left( n+1 \right)\left( 2n+1 \right)}{6}\]

Solution:

Step 1: For n = 1, left side = 1² = 1 and right side =  \frac{1\left( 1+1 \right)\left( 2\times 1+1 \right)}{6}=\frac{1\times 2\times 3}{6}=1
Hence the statement is true for n = 1.

Step 2: Now we assume that the statement to be true for n = m, then

\[{{1}^{2}}+{{2}^{2}}+{{3}^{2}}+….+{{m}^{2}}=\frac{m\left( m+1 \right)\left( 2m+1 \right)}{6}\]

Step 3: Adding the (m + 1)th term i.e., (m + 1)² to both sides we obtain.

\[{{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}}\]

\[\Rightarrow {{1}^{2}}+{{2}^{2}}+{{3}^{2}}+….+{{m}^{2}}+{{\left( m+1 \right)}^{2}}=\frac{\left( m+1 \right)}{6}\left\{ m\left( 2m+1 \right)+6\left( m+1 \right) \right\}\]

\[\Rightarrow {{1}^{2}}+{{2}^{2}}+{{3}^{2}}+….+{{m}^{2}}+{{\left( m+1 \right)}^{2}}=\frac{\left( m+1 \right)}{6}\left\{ 2{{m}^{2}}+7m+6 \right\}\]

\[\Rightarrow {{1}^{2}}+{{2}^{2}}+{{3}^{2}}+….+{{m}^{2}}+{{\left( m+1 \right)}^{2}}=\frac{\left( m+1 \right)\left( m+2 \right)\left( 2m+3 \right)}{6}\]

\[\therefore {{1}^{2}}+{{2}^{2}}+{{3}^{2}}+….+{{m}^{2}}+{{\left( m+1 \right)}^{2}}=\frac{\left( m+1 \right)\left\{ \left( m+1 \right)+1 \right\}\left\{ 2\left( m+1 \right)+1 \right\}}{6}\]

Therefore the statement is true for n = m + 1. Hence by mathematical induction the given statement is true for all positive integers n.

Example 03

Q. Prove by mathematical induction that,

\[{{1}^{3}}+{{2}^{3}}+{{3}^{3}}+….+{{n}^{3}}=\frac{{{n}^{2}}{{\left( n+1 \right)}^{2}}}{4}\]

Solution:

Step 1: For n = 1, left side = 1³ = 1 and right side = \frac{{{1}^{2}}{{\left( 1+1 \right)}^{2}}}{4}=\frac{1\times 4}{4}=1 Hence the statement is true for n = 1.

Step 2: Now we assume the statement is true for n = m, then

\[{{1}^{3}}+{{2}^{3}}+{{3}^{3}}+….+{{m}^{3}}=\frac{{{m}^{2}}{{\left( m+1 \right)}^{2}}}{4}\]

Step 3: Adding the (m + 1)th term i.e., (m + 1)³ to both sides we obtain.

\[{{1}^{3}}+{{2}^{3}}+{{3}^{3}}+….+{{m}^{3}}+{{\left( m+1 \right)}^{3}}=\frac{{{m}^{2}}{{\left( m+1 \right)}^{2}}}{4}+{{\left( m+1 \right)}^{3}}\]

\[\Rightarrow {{1}^{3}}+{{2}^{3}}+{{3}^{3}}+….+{{m}^{3}}+{{\left( m+1 \right)}^{3}}={{\left( m+1 \right)}^{2}}\left\{ \frac{{{m}^{2}}}{4}+\left( m+1 \right) \right\}\]

\[\Rightarrow {{1}^{3}}+{{2}^{3}}+{{3}^{3}}+….+{{m}^{3}}+{{\left( m+1 \right)}^{3}}={{\left( m+1 \right)}^{2}}\left\{ \frac{{{m}^{2}}+4m+4}{4} \right\}\]

\[\Rightarrow {{1}^{3}}+{{2}^{3}}+{{3}^{3}}+….+{{m}^{3}}+{{\left( m+1 \right)}^{3}}=\frac{{{\left( m+1 \right)}^{2}}{{\left( m+2 \right)}^{2}}}{4}\]

\[\Rightarrow {{1}^{3}}+{{2}^{3}}+{{3}^{3}}+….+{{m}^{3}}+{{\left( m+1 \right)}^{3}}=\frac{{{\left( m+1 \right)}^{2}}{{\left( m+1+1 \right)}^{2}}}{4}\]

Therefore the statement is true for n = m + 1. Hence by mathematical induction the given statement is established for all +ve integers.

Example 04

Q. Prove by mathematical induction that,

\[\frac{1}{2.5}+\frac{1}{5.8}+\frac{1}{8.11}+……+\frac{1}{\left( 3n-1 \right)\left( 3n+2 \right)}=\frac{n}{6n+4}\]

Solution:

Step 1: For n = 1, left side = \frac{1}{2.5}=\frac{1}{10}and right side = \frac{1}{6.1+4}=\frac{1}{10} Therefore the statement is true for n = 1.

Step 2: Now we assume the statement to be true for n = m, then

\[\frac{1}{2.5}+\frac{1}{5.8}+\frac{1}{8.11}+……+\frac{1}{\left( 3m-1 \right)\left( 3m+2 \right)}=\frac{m}{6m+4}\]

Step 3: Adding the (m + 1)th term i.e., \frac{1}{\left\{ 3\left( m+1 \right)-1 \right\}\left\{ 3\left( m+1 \right)+2 \right\}}=\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}to both sides we obtain.

\[\frac{1}{2.5}+\frac{1}{5.8}+\frac{1}{8.11}+……+\frac{1}{\left( 3m-1 \right)\left( 3m+2 \right)}+\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}=\frac{m}{6m+4}+\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}\]

\[\Rightarrow \frac{1}{2.5}+\frac{1}{5.8}+\frac{1}{8.11}+……+\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}=\frac{m}{2\left( 3m+2 \right)}+\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}\]

\[\Rightarrow \frac{1}{2.5}+\frac{1}{5.8}+\frac{1}{8.11}+……+\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}=\frac{m\left( 3m+5 \right)+2}{2\left( 3m+2 \right)\left( 3m+5 \right)}\]

\[\Rightarrow \frac{1}{2.5}+\frac{1}{5.8}+\frac{1}{8.11}+……+\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}=\frac{3{{m}^{2}}+5m+2}{2\left( 3m+2 \right)\left( 3m+5 \right)}\]

\[\Rightarrow \frac{1}{2.5}+\frac{1}{5.8}+\frac{1}{8.11}+……+\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}=\frac{\left( m+1 \right)\left( 3m+2 \right)}{2\left( 3m+2 \right)\left( 3m+5 \right)}\]

\[\Rightarrow \frac{1}{2.5}+\frac{1}{5.8}+\frac{1}{8.11}+……+\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}=\frac{m+1}{6m+10}\]

\[\therefore \frac{1}{2.5}+\frac{1}{5.8}+\frac{1}{8.11}+……+\frac{1}{\left( 3m+2 \right)\left( 3m+5 \right)}=\frac{m+1}{6\left( m+1 \right)+4}\]

Therefore the statement is true for n = m + 1. Hence by mathematical induction the given statement is established for all +ve integers.

Example 05

Q. Prove by mathematical induction that, {{2}^{n}}>1for all positive integer n.

Solution:

Let P(n) be the given proposition. Now P(1) implies 2 > 1 which is true. Hence P(1) is true.
Let us assume that P(m) is true. That is {{2}^{m}}>m(induction hypothesis).
Consider {{2}^{m+1}}={{2.2}^{m}}>2mby induction hypothesis.
We know that 2m=m+m\ge m+1for allm\in N.
Therefore, {{2}^{m+1}}>m+1. Hence P(m + 1) is true.
Therefore by mathematical P(n) is true for all n.

Example 06

Q. Show by induction that n\left( n+1 \right)\left( 2n+1 \right) is divisible by 6.

Solution:

Let P\left( n \right)=n\left( n+1 \right)\left( 2n+1 \right)
Now, P\left( 1 \right)=1\left( 1+1 \right)\left( 2.1+1 \right)=6which is divisible by 6.
Let us assume that P(m) is divisible by 6 i,e., m\left( m+1 \right)\left( 2m+1 \right)is divisible by 6.
\Rightarrow m\left( m+1 \right)\left( 2m+1 \right)=6k for some integer k.

\[P\left( m+1 \right)=\left( m+1 \right)\left\{ \left( m+1 \right)+1 \right\}\left\{ 2\left( m+1 \right)+1 \right\}\]

\[\Rightarrow P\left( m+1 \right)=\left( m+1 \right)\left( m+2 \right)\left( 2m+3 \right)\]

\[\Rightarrow P\left( m+1 \right)=\left( m+1 \right)\left( m+2 \right)\left\{ \left( 2m+1 \right)+2 \right\}\]

\[\Rightarrow P\left( m+1 \right)=\left( m+1 \right)\left( m+2 \right)\left( 2m+1 \right)+2\left( m+1 \right)\left( m+2 \right)\]

\[\Rightarrow P\left( m+1 \right)=m\left( m+1 \right)\left( 2m+1 \right)+2\left( m+1 \right)\left( 2m+1 \right)+2\left( m+1 \right)\left( m+2 \right)\]

\[\Rightarrow P\left( m+1 \right)=6k+2\left( m+1 \right)\left( 2m+1+m+2 \right)\]

\[\Rightarrow P\left( m+1 \right)=6k+2\left( m+1 \right)\left( 3m+3 \right)\]

\[\Rightarrow P\left( m+1 \right)=6k+6\left( m+1 \right)\left( m+1 \right)\]

Since each term on the R.H.S. is divisible by 6, their sum is also divisible by 6. Hence P(m + 1) is divisible by 6.
Therefore by induction P(n) is divisible by 6 for all n\in N.

Example 07

Q. Using the principle of mathematical induction show that {{10}^{2n-1}}+1 is divisible by 11 for all n\in N.

Solution:

Let P\left( n \right)={{10}^{2n-1}}+1
NowP\left( 1 \right)={{10}^{2\times 1-1}}+1=10+1=11, which is divisible by 11.
Let us assume thatP\left( m \right)={{10}^{2m-1}}+1which is divisible by 11. Therefore P\left( m \right)={{10}^{2m-1}}+1=11k for some integer k.

\[P\left( m+1 \right)={{10}^{2\left( m+1 \right)-1}}+1={{10}^{2m+1}}+1\]

\[\therefore P\left( m+1 \right)-P\left( m \right)={{10}^{2m+1}}+1-{{10}^{2m-1}}-1\]

\[\Rightarrow P\left( m+1 \right)-P\left( m \right)={{10}^{2m-1}}{{.10}^{2}}-{{10}^{2m-1}}\]

\[\Rightarrow P\left( m+1 \right)-P\left( m \right)={{10}^{2m-1}}\left( {{10}^{2}}-1 \right)\]

\[\Rightarrow P\left( m+1 \right)-P\left( m \right)={{10}^{2m-1}}\times 99\]

Which is clearly divisible by 11.

\[\therefore P\left( m+1 \right)=P\left( m \right)+{{10}^{2m-1}}\times 99\]

\[\Rightarrow P\left( m+1 \right)=11k+{{10}^{2m-1}}\times 9\times 11\]

Therefore P\left( m+1 \right)is divisible by 11.
Hence by the principle of mathematical induction P\left( n \right)is divisible by 11 for all integers n.

<< Previous Topic Predicate and Quantifiers

Next Topic >> Set Theory

;