MAT 140: Discrete Mathematics I Dr. S. Epp

Tips for Success with Proofs and Disproofs

Make sure your proofs are genuinely convincing. Express yourself carefully and completely – but concisely! Write in complete sentences, but don’t use an unnecessary number of words.

Disproof by Counterexample

· To disprove a universal statement, give a counterexample.

· Write the word "Counterexample" at the beginning of a counterexample.

· Write counterexamples in complete sentences.

· Give values of the variables that you believe show the property is false.

· Include the computations that prove beyond any doubt that these values really do make the property false.

All Proofs

· Write the word “Proof” at the beginning of a proof.

· Write proofs in complete sentences.

· Start each sentence with a capital letter and finish with a period.

Direct Proof

· Begin each direct proof with the word "Suppose."

· In the "Suppose" sentence:

a. Introduce a variable or variables (indicating the general set they belong to - e.g., integers, real numbers etc.), and

b. Include the hypothesis that the variables satisfy.

· Identify the conclusion that you will need to show in order to complete the proof.

· Reason carefully from the “suppose” to the “conclusion to be shown.”

· Include the little words (like “Then,” “Thus,” “So,” “It follows that”) that make your reasoning clear.

· Give a reason to support each statement you make in your proof.

Proof by Contradiction

· Begin each proof by contradiction by writing “Suppose not. That is, suppose...,” and continue this sentence by carefully writing the negation of the statement to be proved.

· After you have written the “suppose,” you need to show that this supposition leads logically to a contradiction.

· Once you have derived a contradiction, you can conclude that the think you supposed is false. Since you supposed that the given statement was false, you now know that the given statement is true.

Proof by Contraposition

• Look to see if the statement to be proved is a universal conditional statement.
• If so, you can prove it by writing a direct proof of its contrapositive.

Proof by Mathematical Induction

Mathematical induction is used to prove properties about integers. A proof by mathematical induction consists of two parts.

• In part 1, show that the property is true for some initial integer.
• In part 2, show that for each integer k ³ the initial integer, if the property is true for k then it is true

for k + 1.