Induction is a form of proof useful for proving equations involving non-closed expressions (i.e., expressions with terms; sequences).

Explanation

edit

Induction involves first proving that the equation is true for  , then proving true for   (assuming for the purpose of the proof that the equation holds true for  ). Since it is true for   and true for  , and also true for  , it is true for  . It follows that it is true for all positive integers  .

Examples

edit

Proving the formula for the sum of a series

edit

Q: Prove by mathematical induction that for all integers  ,

 

A:

  1. When  ,  , so it is true for  
  2. Suppose that the statement is true for  . That is, suppose that  . This is sometimes called the induction hypothesis.
  3. Then prove the statement for   (that is, prove that  :
     
  4. It follows from parts 1 and 2 by mathematical induction that the statement is true for all positive integers  .