Main or Advanced/AIEEE

Writing Proofs using Mathematical Induction

The solution in mathematical induction consists of the following steps:

Proving identities related to natural numbers

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

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,
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