The Learning Point‎ > ‎Mathematics‎ > ‎

Principle of Mathematical Induction- A Tutorial with solved problems- Identities involving Natural Numbers, Trigonometric Ratios




 
IIT-JEE Mathematics
Our Price: Rs.325
Buy from FlipKart
 

Objective Mathematics For IIT...
List Price: Rs.850
Our Price: Rs.765
Buy from FlipKart
 
IIT-JEE Mathematics Challenge...
List Price: Rs.440
Our Price: Rs.418
Buy from FlipKart
 
Higher Algebra 50th Edition
List Price: Rs.165
Our Price: Rs.157
Buy from FlipKart
 
Advanced Algebra
List Price: Rs.495
Our Price: Rs.460
Buy from FlipKart
 
Board + PMT/ IIT Foundation f...
List Price: Rs.1050
Our Price: Rs.735
Buy from FlipKart
 
Objective Mathematics For IIT...
List Price: Rs.850
Our Price: Rs.765
Buy from FlipKart
 
Target IIT Mathematics
List Price: Rs.515
Our Price: Rs.464
Buy from FlipKart
 
33 Years IIT-JEE 9 yrs AIEEE...
List Price: Rs.290
Our Price: Rs.276
Buy from FlipKart
 
TARGET IIT MATHEMATICS FOR II...
List Price: Rs.495
Our Price: Rs.470
Buy from FlipKart


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 

Main or Advanced/AIEEE

, and anyone else who needs this Tutorial as a reference!


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.

Tutorial with solved problems of an Elementary Level (Elementary Problem Set A):





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

Adding 3 both sides,
(3m+2) +3 < (m+4)
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 Numbers
Introduction 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 Induction Introductory problems related to Mathematical Induction.Quadratic Equations
Introducing 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 Progressions
Arithmetic, 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.
 




 


Try out our Quizzes!