Mathematical Induction

    Many statements in mathematics are true when the symbols represent a set of all numbers, such as say, the natural numbers, the integers, the rational numbers, the real numbers, and even the complex numbers. But there are some statements that are peculiar to the natural numbers; and frequently such a statement can be proven to be true by using mathematical induction. Basically, mathematical induction states that if a set of positive integers has two properties:

    (1) the integer 1 is in the set and secondly,
    
    (2) if the set has an integer, then it must contain the next integer,
    
then the set must be the positive integers.
    The induction principle is analogous to an infinite string of dominos set up in a single line arranged so that if one falls down then so does the next one. Now suppose that you knock down the first domino, and then after some time has passed you check back and the dominos are stilling falling. Would you believe that this will continue indefinitely?   
    The method of proof by using the Principle Mathematical Induction is frequently useful in the theory of numbers. Familiarity with this type of argument is essential to subsequent work.

Proposition (Principle of Mathematical Induction) Let be a set of positive integers with the following property:

    (i) The integer 1 belongs to
    
    (ii) If is in then is in
    
Then is the set of positive integers.

    Proof. Let be the set of all positive integers not in and assume that is not empty. The Well-Ordering Principle states that must have a least element, say However, by (i) 1 is in and so it follows that and and therefore, is not in Then by (ii), is in which contradicts that lies in Therefore, is empty and so is the set of positive integers.

    In any proof by mathematical induction, we must not forget to show that is in Even if we show that the truth of in implies that is in if is not in then we cannot conclude that is the set of positive integers. For example, let be the set of all positive integers that satisfies: Suppose satisfies, Using this we have, so also satisfies: So, if satisfies: then, it would follow that is true for all positive integers However, since does not satisfy it is not true. In fact, is false for all positive integers
    The next result states that the Well-Ordering Principle and the Principle of Mathematical Induction are equivalent. So in fact, either one can be used as an axiom.

Proposition (Mathematical Induction - Well Ordering Equivalence) If a set of positive integers has the two properties (i) the integer 1 belongs to and (ii) whenever the integer is in the next integer must also be in   then is the set of positive integers; then every set of positive integers must a have a least element.

    Proof. Assume that there exists a nonempty set of positive integers, say that does not have a least element. Because is the smallest positive integer, is not in and so is smaller than all integers in Let be the set of all positive integers that are less than all the integers in At least is in and so is nonempty. Suppose that is in If is in then by the Principle of Mathematical Induction must be the set of all positive integers, and thus is empty and so every set of positive integers must have a least element. If is not in then is the least integer in which contradicts the definition of Therefore, if is a nonempty set of positive integers, then must have a least integer.

Example (Mathematical Induction) Use mathematical induction to prove that



for all positive integers

    Solution. For Assume that the result is true for a positive integer we need to show that   holds. We have,

Example (Mathematical Induction) Use mathematical induction to prove that for all positive integers

    Solution.  For Assume that the result is true for a positive integer we need to show that   holds. We have,


    

Example (Mathematical Induction) Use mathematical induction to prove that



for all positive integers

    Solution. For Assume that the result is true for a positive integer we need to show that   holds. We have,


    

Example (Mathematical Induction) Use mathematical induction to prove that



for all positive integers

    Solution. Since the statement is true for Assume that the result is true for a positive integer we need to show that   holds. Starting from we multiply by 2 to obtain But since Therefore, as desired.

Example (Mathematical Induction) Let be any real number greater than . Use mathematical induction to prove that for all positive integers

    Solution. Since the statement is true for Assume that the result is true for a positive integer we need to show that   holds. Since we can multiply by to obtain


    
Since we see that



as desired.

Proposition (Mathematical Induction - 2nd Principle) A set of positive integers that contains the integer 1, and that has the property: for every positive integer if the set contains then it also contains the integer must be the set of all positive integers.

    Proof. Let be the set with the stated property and let be the set consisting of all positive integers not in Assuming that is nonempty, we can choose to be the least integer in Then and so none of the integers lies in Then by the second property, is in which contradicts the definition of Thus, is empty and must be the set of all positive integers.

Example (Mathematical Induction - 2nd Principle) Use the second principle of mathematical induction to establish that for all



    Solution. For is obvious. Suppose that the equation is true for namely,
    


Then for we have,



and so



We can also rely on the 2nd Principle of Mathematical Induction, by considering the formula:

    The assumption that "the statement is true for " will often be referred to as the induction hypothesis. Sometimes the role that 1 plays in the Principle of Mathematical Induction will be replaced by some other integer, say in such instances the Principle of Mathematical Induction establishes the statement for all integers
    The method of Mathematical Induction has its limitations in that it consists of testing a known (or conjectured) formula. All that the induction  process enables us to do is to show that any special case can be proved on the assumption that all the preceding cases have been verified.

• print this page
• pages linking here
• related pages