Let P(n) :
I.   For n = 1,
    

∴     P(1) is true
II.  Let the statement be true for n = m, 

∴    P(m):                           ...(i)
III.  For n = m + 1,
      
or 
or       ... (ii)

                                (Note that the last but one term in (ii) is always the same as last term in (i)]
        From (i),

∴   


        which is true

∴      P (m + 1) is true.

∴      P(m) is true P(m + 1) is true.
Hence, by the principal of mathematical induction, P(n) is true for all