• Unit 4: Mathematical Induction and Proofs

    So far, we have learned about symbology, truth tables, writing equations, and determining how many units could be in a set under specific circumstances. We have done all of this has under the assumption that we can easily see the results of our efforts. However, in practical situations that you will encounter in real life with serious applications, we cannot always see our results quickly, or necessarily even traverse the situation easily. For that, we must turn to the methods behind mathematical systems and proofs. These allow us to "get the big picture" without having to visualize it all at once. Proofs also give us a way to consider all of the available information in a given arrangement of facts, even when some of the "facts" might not actually be true. They also have the added advantage of letting us ignore whole portions of a situation when we know they do not hold the answer we seek.

    Completing this unit should take you approximately 5 hours.

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

      • discuss how one conclusion leads to another, in the mathematical sense, for a given situation;
      • write the terms of a logical sequence as a generalized formula;
      • use mathematical induction to prove the validity of logical sequences; and
      • employ inductive reasoning to situations where there is sufficient evidence to warrant generalization.

    • 4.1: Mathematical Systems

      • Mathematical Systems Page

        This page gives an overview of what a mathematical system is and how logic plays an important role in such systems. A discussion on how mathematical facts are developed and organized will help to unify the concepts presented later in the course. The system of propositions and logical operators we developed earlier will serve as a model for our discussion.

    • 4.2: Direct Proof

      • Direct Proof Page

        "Brute force" is a term commonly applied to considering all possibilities manually, one at a time, before coming to a conclusion. That works well under simple circumstances but is rarely practical within industrial applications. This section discusses that reality so that you can avoid the "brute force" trap.

    • 4.3: Indirect Proof

      • Indirect Proof Page

        Science works to either prove or disprove assertions. This is contrary to those who insist that science seeks only to disprove assertions. This mentality causes the acceptance of assertions unless they are proven false. Therein lies a dangerous way of thinking since it leads to "guilty until proven innocent" once an accusation is made. Assertions are not acceptable as fact until they are proven true. In this section, we consider "proof by contradiction", one side of scientific effort.

      • Try It Now Book

        Work these exercises to see how well you understand this material.

    • 4.4: Propositions over a Universe

      • Propositions and Truth Sets Page

        As one enters into the realm of advanced technology, one increasingly realizes that a layman's use of terminology and language is too imprecise. Not only does the use of technology require precision, but so does its discussion. Otherwise, it is not possible to establish requirements for a project. Nor is it possible to discover the cause of system problems and thereby get a sense of where to focus one's energies. This subunit gets you thinking along those lines and helps you to understand and avoid the vagueness of common speech.

      • Try It Now Book

        Work these exercises to see how well you understand this material.

    • 4.5: Mathematical Induction

      • Discussion and Examples Page

        Induction is a means of proving a theorem by showing that if the theorem or assertion is true of any particular case, it is true of the next case in a series, and then showing it is indeed true in any particular case. Our text applies that definition to mathematics by saying mathematical induction is a technique for proving propositions over the positive integers. Mathematical induction reduces to a finite number of steps the proof that all positive integers belong to a specific truth set. The number of steps to complete the proof is the same, regardless of the size of the set or the number of positive integers involved. This is crucial to our discussion of discrete mathematics since it allows us to consider large volumes of evidence while deciding whether to accept or reject an assertion. As we develop automated systems or simply consider what we are hearing on the evening news, we find ourselves having to do exactly that.

    • 4.6: Strong Induction

      • Strong Mathematical Induction Page

        Also known as course-of-values induction, strong induction adds to mathematical induction by showing that additional assertions hold if mathematical induction holds.

      • Try It Now Book

        Work these exercises to see how well you understand this material.

    • Unit 4 Assessment

      • Unit 4 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.