The Learning Point‎ > ‎Mathematics‎ > ‎

### The Principle of Mathematical Induction with Examples and Solved Problems

Target Audience: High School Students, College Freshmen and Sophomores, Class 11/12 Students in India preparing for ISC/CBSE and Entrance Examinations like the IIT-JEE

, and anyone else who needs this Tutorial as a reference!
Principle of Mathematical Induction

## Writing Proofs using Mathematical Induction

Induction is a way of proving mathematical theorems. Like proof by contradiction or direct proof, this method is used to prove a variety of statements. Simplistic in nature, this method makes use of the fact that if a statement is true for some starting condition, and then it can be shown that the statement is true for a general subsequent condition, then, it is true in general. Formally, if we show that a statement is true for an integer n>4, and then we show that it is true for some integer k+1 if it is true for the integer k(k is greater than or equal to 4), then we have shown that it is true for all integers greater than 4.

## The solution in mathematical induction consists of the following steps:

• Write the statement to be proved as P(n) where n is the variable in the statement, and P is the statement itself. Example, if we are to prove that 1+2+3+4+. . . .+n=n(n+1)/2, we say let P(n) be 1+2+3+4+. . .+n=n(n+1)/2.
• Show that the basis step is true. If we are to show that P(n) is true for all integers greater than or equal to 3, then basis step comprises of showing that P(3) is true.
• Assume that P(k) is true for some k greater than the basis step. Then, prove that P(k+1) is true using basis step and the fact that P(k) was true.
• Once P(k+1) has been proved to be true, the statement is true for all values of the variable, by Principle of Mathematical Induction.
• Mathematical Induction is very obvious in the sense that its premise is very simple and natural.

Here are some of the questions solved in this tutorial:

### Proving identities related to natural numbers

Q:  Prove that 1+2+3+…+n=n(n+1)/2 for all n, n is Natural.

Q: Prove that 3n>n is true for all natural numbers.

Q: Prove that n^2+n is even for all natural numbers n.

Q: Prove that 23n-1 is a multiple of 7 for all n, where n is a natural number.

Q: Prove that 7+77+777+7777+777…7(n digits)=7(10n+1-9n-10)/81

### Many trigonometric and algebraic laws can be verified easily using the PMI.

When in doubt about a certain identity, use PMI to quickly verify the truth of the complex formula you are using.

## More Challenging Problem on Mathematical Induction (Advanced Set B)

Question 1)

Prove that (n+1)! >2n  for all n>1.

Question 2)

Prove that cos(x-180n) = (-1)n cosx.

Question 3)

If a = 1     ,  then prove that  dna/dxn = (-1)n n!

x+5                                                 (x+5)n+1

Question 4)

Prove that 3n+2 < (n+4)2   by using mathematical induction.

Question 5)

Prove that product of any three numbers ocurring one after the other is divisible by 6.

Question 6)

Prove that exactly one among n+10,n+12 and n+14 is divisible by 3,considering n is always an natural number.

Question 7)

Prove that cube of any three consecutive natural numbers is divisible by 9 using mathematical induction.

Question 8)

Prove by mathematical induction

1    +       1    + …..... .=  1   (   1    -                1          )

1.2.3.4      2.3.4.5                    3    1.2.3      (n+1)(n+2)(n+3)

Question 9)

Prove that the equation n(n3 - 6n2  +11n -6) is  always divisible by 4 for n>3.Use mathematical induction.

Question 10)

Prove that 6n  + 10n - 6 contains 5 as a factor for all values of n by using mathematical induction.

Question 11)

Prove that (n+ 1/n)3 > 23   for n being a natural number greater than 1 by using mathematical induction.

Question 12)

Prove that 2n + 3n < 5n  holds for n>1 .

Questions with solutions of problems (Advanced Set B)

Question 1)

Prove that (n+1)! >2n  for all n>1.

Solution 1)

Let us assume this equation as equation 1).

Putting n=2 in equation 1),we get,

3! > 22

3! > 4

Since this is true,therefore the equation holds true for n=1.

Let us assume that equation holds true for n=m,

(m+1)! > 2m .equation 2)

Now we have to prover that this equation holds true for n=m+1 ,i.e,

(m+2)! > 2m+1 .

From equation 2)

(m+1)! > 2m .

Multiply above equation by m+2

(m+2)! > 2m (m+2)

> 2m+1  + 2m.m

> 2m+1.

Hence proved.

Question 2)

Prove that cos(x-180n) = (-1)n cosx.

Solution 2)

Let us assume this equation as equation 1)

Putting n=1,in equation 1),we get

cos(x-180)=-cosx.

This is true,(try to recall trignometric properties),therefore this equation is satisfied for n=1.

Let us assume that this equation holds true for n=m.

cos(x-180m) = (-1)mcosx  equation 2)

Now we need to prove that equation 2) also holds true for n=m+1

That is we need to prove cos(x-180(m+1))=(-1)m+1cos(x)

LHS = cos(x- 180m - 180) =-cos(x-180m)

= -(-1)m cosx

{using the identity cos(y-180) = -cosy and considering y=x-180m

and also using equation 2)}

we can write,

cos(x-180(m+1)) = (-1)m+1 cosx .

Since LHS=RHS

Hence proved.

Question 3)

If a = 1     ,  then prove that  dna/dxn = (-1)n n!

x+5                                                 (x+5)n+1

Solution 3)

Let us assume the equation given in the question as equation 1),

Putting n=1 ,in equation 1,

LHS = da/dx =    -1

(x+5)2

RHS = -1

(x+5)2

Since LHS = RHS ,therefore ,equation 1) holds true for n=1.

Let us assume that equation 1) holds true for n=m,

Therefore, dm a/dxm = (-1)m m! .            -------equation 2)

(x+5)m+1

Now,we need to prove that the equation holds true for n = m+1

dm+1a/dxm+1 = (-1)m+1 (m+1)!

(x+5)m+2

From equation 2)

dma/dxm  = (-1)m  (m)!

(x+5)m+1

differentiating equation 2) ,we get

LHS =

d (dma / dxm ) = dm+1a/dxm+1

dx

dm+1a/dxm+1 = -(-1)m  m!(m+1)

(x+5)m+2

= (-1)m+1  (m+1)!

(x+5)m+2

=RHS

Since,LHS = RHS

Hence proved.

Question 4)

Prove that 3n+2 < (n+4)2

Solution 4)

Let us assume the above equation as equation 1)

Putting n=1 ,in the equation ,we get

LHS = 3(1)+2 = 5

RHS = (1+4)2 = 25

Since LHS < RHS

Hence,the equation holds true for n=1.

Let us assume that the equation holds true for n=m,

i.e. assume equation 2) holds true

3m+2 < (m+4)2  ----------------------2)

Now,we need to prove that the equation holds true for n=m+1

3(m+1) + 2 < (m+5)2

LHS = 3(m+1) +2

=3m + 3 + 2

=(3m + 2) +3

From equation 2)

(3m+2)  < (m+4)2

2 + 3

< m2 + 16 + 8m + 3

< m2 + 8m + 18

After adding  (2n+ 7) on RHS also LHS < RHS ,since RHS will be still greater than LHS after adding something.

(3m+2) +3<  m2 + 8n + 18 + (2n+7)

<  m2 + 10m + 25

< (m+5)2

Since 3(m+1) +2 < (m+5)2

Since,LHS < RHS

for n=m+1 ,

Hence proved.

Question 5)

Prove that product of any three numbers ocurring one after the other is divisible by 6.

Solution 5)

Let us assume that the product of these numbers is n(n+1)(n+2)-----------------1)

Putting n=1 in equation 1) ,we get

1(2)(3) = 6

Therefore,this is divisible by 6.

Assuming equation 1) holds true for n=m.

Therefore,m(m+1)(m+2) = 6k

Now,we need to prove that equation 1) holds true for n=m + 1

We need to prove that (m+1)(m+2)(m+3) is divisible by 6.

(m+1)(m+2)(m+3) = m(m+1)(m+2) + 3(m+1)(m+2)

= 6k + 3(m+1)(m+2)

Since we know that if two numbers are occuring one after the other exactly one among them is even and one among them is odd.

Therefore,in 3(m+1)(m+2),one of either (m+1) or (m+2) will be even and so will contsin atleast one two.Therefore 3(m+1)(m+2) will definitely contain a term of 6.

Hence proved.

Question 6)

Prove that exactly one among n+10,n+12 and n+14 is divisible by 3,considering n is always an natural number.

Solution 6)

For n=1,

n+10=11

n+12=13

n+14=15

Exactly one i.e 15 is divisible by 3.

Let us assume that that for n=m exactly one out of n+10,n+12,n+14 is divisible by 3

Case 1)Let us assume that for n=m ,m+10 was divisible by 3

Therefore,m+10 = 3k

m+12 = 3k+2

m+14 = 3k+4

We need to prove that for n=m+1 ,exactly one among them is divisible by 3.Putting m+1 in place of n ,we get

(m+1)+10=m+11=3k + 1 (not divisible by 3)

(m+1)+12=m+13= 3k+3 =3(k+1) (divisible by 3)

(m+1)+14=m+15=3k+5 (not divisible by 3)

Therefore,for n=m+1 also exactly one among the three,n+10,n+12 and n+14 is divisible by 3.

Similarly we can prove that exactly one among three of these is divisible by 3 by considering cases when n+12=3k and n+14 = 3k.

Question 7)

Prove that cube of any three consecutive natural numbers is divisible by 9 using mathematical induction.

Solution 7)

Let us assume the three consecutive numbers as n,n+1 and n+2.

Therefore,according to the question,

n3 +(n+1)3 + (n+2)3 ---------1) should be divisible by 9  .

Putting n=1 in equation 1),we get

equation 1) as equal to 36.

Since 36 is divisible by 9,therefore equation 1) is divisible by 9 for n=1.

Let us assume that equation 1) holds true for n=m.

Therefore,m3 + (m+1)3  + (m+2)3 = 9k -----------------2) where k is a natural number

Now,we need to prove that equation 1) holds true for n=m+1.

Putting n=m+1 in equation 1)

(m+1)3 + (m+2)3 + (m+3)3 --------------3)

We need to prove that equation 3) is a divisible by 9

Putting equation 2) in equation 3 , we get ,

(m+1)3 +(m+2)3 + (m+3)3 = 9k - m3 +(m+3)3

= 9k - m3 +m2 + 27 + 9m(m+3)

= 9(k +3+m(m+3))

We can see that for n=m+1 also equation 1) contains a factor of 9.

Hence proved.

Question 8)

Prove by mathematical induction

1    +       1    + …..... .=  1   (   1    -                1          )

1.2.3.4      2.3.4.5                    3    1.2.3      (n+1)(n+2)(n+3)

Solution 8)

Let us consider this equation as equation 1)

Putting n=1 in equation 1),we get

LHS =         1

1.2.3.4

RHS = 1 [    1   -      1    ]

3   1.2.3     2.3.4

= 1.1.3

2.3.3.4

=   1

1.2.3.4

Since LHS = RHS,

Then,equation 1) holds true for n=1

Let us assume that equation 1) is true for n=m

1    +       1    + …..... .=  1   (   1    -                1          )  ----------------2)

1.2.3.4      2.3.4.5                    3    1.2.3      (m+1)(m+2)(m+3)

Now,we should prove that equation 1) is true also for n=m+1

i.e we need to prove sum of n terms equal to  1   (   1    -                1          )

3     1.2.3      (m+2)(m+3)(m+4)

LHS =            1    +       1    + ….....   1                         +                                 1

1.2.3.4      2.3.4.5               m(m+1)(m+2)(m+3)       (m+1)(m+2)(m+3)(m+4)

|                             |

(n+1)th term

From equation 2),we can write the sum of first n terms as

=         1   (   1    -                1          )   +                                   1

3    1.2.3      (m+1)(m+2)(m+3)         (m+1)(m+2)(m+3)(m+4)

=     1   (   1    -                1          )    = RHS

3     1.2.3      (m+2)(m+3)(m+4)

Therefore,since LHS = RHS

Hence proved.

Question 9)

Prove that the equation n(n3 - 6n2  +11n -6) is  always divisible by 4 for n>3.Use mathematical induction.

Solution 9)

This equation can be factorized as

n(n-1)(n-2)(n-3)   ----------------------1)

Putting n=4 in equation 1)

Then equation 1) is divisible by 4.

Therefore,for n=1 ,equation 1) is satisfied.

Let us assume that for n=m equation 1) is divisible by 4.

m(m-1)(m-2)(m-3) = 4k where k is a natural number

Now,we need to prove that for n=m+1 also equation 1) is divisible by 4.

Putting n=m+1 in equation 1) we get

(m+1)(m)(m-1)(m-2)----------------3)

Equation 3) can be written as

(m-3+4)(m)(m-1)(m-2)

=(m-3)(m)(m-1)(m-2) + 4(m(m-1)(m-2))

=4k + 4 x product of natural numbers

Since for n=m+1 also equation 1) is divisible by 4.

Hence proved.

Question 10)

Prove that 6n  + 10n - 6 contains 5 as a factor for all values of n by using mathematical induction.

Solution 10)

Let us assume 6n  + 10n - 1 as equation 1)

Putting n=1 in equation 1),we get

6 + 10 -6= 10

which is divisible by 5.

Let us assume that equation 1) has 5 as a factor for n=m

therefore,    6m  + 10m - 6 = 5k ----------------2)

Now we need to prove that equation 1) is divisible by 5,for n=m+1

Putting n=m+1 in equation 1),we get

6m+1 + 10(m+1) -6 = 6m+1 + 10m +10 -6

= 6(  6m  -1) + 10(m+1)--------------3)

{ Here ,we need to prove that 6m  -1 is factor of 5 ,which can be proved using equation 2)

6m  -1 = 5k -10m + 5  and put this in equation 3)}

=5.6(k-2m+1) +5.2 (m+1)

=5(6k-12m+1+2m+2)

Therefore,equation 1) contains a factor of 5,for n=m+1

Hence proved.

Question 11)

Prove that (n+ 1/n)3 > 23   for n being a natural number greater than 1 by using mathematical induction.

Solution 11)

Let us assume (n+ 1/n)3 > 23     as equation 1)

Putting n=1 in LHS of equation 1),we get

LHS = (2 + ½)3 =15.625

RHS = 8

Since LHS > RHS ,therefore the equation is true for n=1.

Let us assume that the equation is true for n=m

i.e (m+ 1/m)3 > 23

Now,we need to proof that the equation is true for n=m+1

i.e we need to prove that ((m+1) + 1/(m+1))3 >23

1/m and 1/(m+1) are fractions,they are less less then 1they dont make any much difference

Since we know that

1+1/(m+1)  > 1/m------2) { Since LHS is greater than 1 and RHS is always smaller than 1

Adding m both the sides in equation 2),we get

(m+1) +1/(m+1)  > m+1/m

Cubing both the sides we get

((m+1)+ 1/(m+1))3     > (m+1/m)3  > 23

Therefore ,  ((m+1)+ 1/(m+1))3  > 23

Hence proved.

Question 12)

Prove that 2n + 3n < 5n  holds for n>1

Solution 12)

Let us name the equation  2n + 3n > 5n as equation 1) .

Noe putting n=2 ,in equation 1) we get

LHS = 22 + 32

= 13

RHS= 52

=  25

LHS < RHS

therefore,equation 1) holds true for n=2.

Now ,let us assume that equation 1 is true for n=m.

2m + 3m < 5m --------------2)

Now ,we need to prove that  2n+1 + 3n+1 < 5n+1

Now,from equation 2),we know that,

2m + 3m < 5m

Multiplying 5 in above equation,we get

5(2m + 3m )< 5.5m

< 5m+1

We know that 2m .5 > 2m+1  and  3m .5 > 3m+1 since 5>2 and 5>3

This gives that

2m+1 + 3m+1 < 5(2m + 3m ) < 5m+1

Hence proved.

References:

NCERT text book

http://www.algebra.com/algebra/homework/real-numbers/real-numbers.faq.question.242615.html

http://math.stackexchange.com/questions/tagged/induction

http://www.algebra.com/algebra/homework/word/numbers/Numbers_Word_Problems.faq.question.478538.html

http://hsc.csu.edu.au/maths/ext1/math_induction/179/mathinduc.htm

http://home.cc.umanitoba.ca/~thomas/Courses/F10WInductionSolns.pdf

You might like to take a look at our other algebra tutorials:

 Introduction to Complex NumbersIntroduction to Complex Numbers and iota. Argand plane and iota. Complex numbers as free vectors. N-th roots of a complex number. Notes, formulas and solved problems related to these sub-topics. The Principle of Mathematical InductionIntroductory problems related to Mathematical Induction. Quadratic EquationsIntroducing various techniques by which quadratic equations can be solved - factorization, direct formula. Relationship between roots of a quadratic equation.  Cubic and higher order equations - relationship between roots and coefficients for these. Graphs and plots of quadratic equations. Quadratic Inequalities Quadratic inequalities. Using factorization and visualization based methods. Series and ProgressionsArithmetic, Geometric, Harmonic and mixed progressions. Notes, formulas and solved problems. Sum of the first N terms. Arithmetic, Geometric and Harmonic means and the relationship between them.

After reading this tutorial you might want to check out some of our other Mathematics Quizzes as well.
 Quizzes on ProgressionsMCQ #1: Arithmetic Progression MCQ #2: Geometric ProgressionMCQ #3 : More on Geometric Progressions.MCQ #4 : Harmonic Progressions. MCQ #5: More on Harmonic ProgressionMCQ #6: Mixed ProgressionsComplex NumbersMCQ #1MCQ #2: More on Complex NumbersQuadratic EquationsMCQ Quadratic EquationsQuadratic In-equationsMCQ Quadratic In-equations Coordinate Geometry - Straight LinesMCQ #1: Cartesian Planes, Straight Line BasicsMCQ #2 on Straight LinesMCQ #3 on Straight LinesMCQ #4 on Straight LinesCircles1 MCQ #1 on Circles. 2 MCQ #2 on Circles. 3 MCQ #3 on Circles. Conic Sections- Parabola, Hyperbola, Ellipse1 MCQ- The Basics of Conic Sections2 MCQ on Parabola..3 MCQ on Hyperbola4 MCQ on Ellipses. ProbabilityMCQ #1 on Basic ProbabilityMCQ #2: More Challenging Problems on ProbabilityMCQ #3- Conditional Probability and Bayes Theorem