• Unit 5: Mathematical Induction

    In this unit, you will prove propositions about an infinite set of positive integers. Mathematical induction is a technique used to formulate all such proofs. The term recursion refers to a method of defining sequences of numbers, functions, and other objects. The term mathematical induction refers to a method of proving properties of such recursively defined objects.

    Completing this unit should take you approximately 4 hours.

    • Upon successful completion of this unit, you will be able to:

      • recognize the various forms and equivalences of mathematical induction;
      • use mathematical induction to prove formulas for summations and products;
      • use mathematical induction to prove inequalities; and
      • use mathematical induction to prove properties about remainders.

    • 5.1: Mathematical Induction Is Equivalent to the Well-Ordering Property of N

      • Induction Page

        Watch these videos, which provide informative discussions as to why the well-ordering principle of the natural numbers implies the principle of mathematical induction and discuss why the principle of strong mathematical induction implies the well-ordering principle of the natural numbers.

      • Mathematical Induction Page

        Watch this video, which provides an informative discussion on the principle of mathematical induction and the well-ordering principle of the natural numbers. It specifically addresses the notion of strong mathematical induction.

    • 5.2: Proofs of Summations and Products

        • 5.2.1: Sums and Products

          • Proof by Induction Page

            Watch this video, which examines how the principle of mathematical induction is used to prove statements involving sums and products of integers.

        • 5.2.2: Divisibility

        • 5.2.3: Recursively Defined Functions

          • Old Dominion University: Shunichi Toida's "Recursive Definition" URL

            Read these essays. Notice the similarities between using recursion to define sets and using recursion to define functions. Then answer the four questions at the end of the first essay.

            In this type of definition, first a collection of elements to be included initially in the set is specified. These elements can be viewed as the seeds of the set being defined. Next, the rules to be used to generate elements of the set from elements already known to be in the set (initially the seeds) are given. These rules provide a method to construct the set, element by element, starting with the seeds. These rules can also be used to test elements for the membership in the set.

          • Hard Inequality Page

            Watch this video, which illustrates using the principle of strong mathematical induction to prove a statement about divisibility of natural numbers.

      • Unit 5 Assessment

        • Unit 5 Assessment Quiz
          Receive a grade

          Take this assessment to see how well you understood this unit.

          • This assessment does not count towards your grade. It is just for practice!
          • You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
          • You can take this assessment as many times as you want, whenever you want.