Proof Methods and Strategy

15 min read

Quick Reference

Field	Value
Textbook	Rosen, Discrete Mathematics and Its Applications, 8th edition
Chapter	1 (The Foundations: Logic and Proofs)
Section	1.8 (Proof Methods and Strategy)
Subsections	1.8.1 Introduction; 1.8.2 Exhaustive Proof and Proof by Cases; 1.8.3 Existence Proofs; 1.8.4 Uniqueness Proofs; 1.8.5 Proof Strategies
Pages	96-120

Try This First

📋 A three-minute warm-up before any formal method (click to open)

Take the claim: “For every integer $n$, the number $n^2 + n$ is even.”

Pick four integers of your own (try a negative one, zero, an odd one, and an even one). For each, compute $n^2 + n$ and check whether the result is even.

Question: After four successes, have you proved the claim for every integer? If not, what would a complete argument need to handle that four examples cannot?

What did you find?

Every value you tried came out even. For example, $n = 3$ gives $9 + 3 = 12$, and $n = -2$ gives $4 - 2 = 2$.

Four examples do not prove a statement about all integers, because infinitely many integers remain unchecked. A complete argument has to cover every integer at once. One clean way: split the integers into two groups, the even ones and the odd ones, and show the claim holds for each group. That split is exactly proof by cases.

Choosing a Method, Then Carrying It Out

Sections 1.7 and 1.8 together form a toolbox. Section 1.7 supplies the three workhorse methods for a conditional statement: direct proof, proof by contraposition, and proof by contradiction. Section 1.8 adds the methods that handle the other common shapes of mathematical claims. A statement whose hypothesis splits into separate situations is handled by proof by cases. A claim that something exists is handled by an existence proof. A claim that something exists and is the only one is handled by a uniqueness proof. A claim that something is false for every member of a domain is settled by a single counterexample.

The skill is two-sided. First, read the shape of the statement and pick a method that fits that shape. Second, carry the method out without gaps. Each method pairs with the kind of statement that signals it.

Prerequisite Hub

Builds on:

Skill	Why it is needed
Introduction to Proofs (`dm-introduction-to-proofs`)	Proof by cases, existence proofs, and counterexamples all reuse the direct proof, proof by contraposition, and proof by contradiction from Section 1.7. The reader must already write a clean direct argument and recognize a vacuous or trivial proof.

Unlocks:

Skill	What it uses from here
Mathematical Induction (`dm-mathematical-induction`)	Induction is a structured proof method for statements about all positive integers, and its basis-and-step format is a disciplined relative of the case-splitting practiced here.
Sets (`dm-sets`)	Set identities such as $A \cup B = B \cup A$ are proved by the methods of this section, often by showing two set inclusions as two cases.
Functions (`dm-functions`)	Proving a function is one-to-one or onto uses existence and uniqueness arguments built here.

Cross-course prerequisites: none.

Proof by Cases

When the hypothesis of a conditional statement naturally breaks into separate situations, a single direct argument may not reach all of them. The fix is to argue each situation on its own.

The Official Definition

Proof by cases (Rosen 8e, Section 1.8):

To prove a conditional statement of the form $(p_1 \vee p_2 \vee \cdots \vee p_n) \rightarrow q$, the tautology $[(p_1 \vee \cdots \vee p_n) \rightarrow q] \leftrightarrow [(p_1 \rightarrow q) \wedge \cdots \wedge (p_n \rightarrow q)]$ can be used as a rule of inference. This shows that the original conditional statement with a hypothesis made up of a disjunction can be proved by proving each of the conditional statements $p_i \rightarrow q$ individually. Such an argument is called a proof by cases.

Source: Rosen 8e, Section 1.8, subsection 1.8.2 Exhaustive Proof and Proof by Cases, p.97-98.

Two requirements keep a case proof honest. The cases must be exhaustive, meaning every possibility in the domain falls into at least one case. The work inside each case must be complete, meaning $q$ is established under that case’s assumption. A related method, exhaustive proof, simply checks a claim across a finite list of possibilities one at a time, which is a proof by cases where each case is a single value.

Worked Example: Splitting Into Even and Odd

Claim. For every integer $n$, the number $n^2 + n$ is even.

Predict first. Before reading the proof, predict how many cases this claim needs and what the natural split is.

Check your prediction

Every integer is either even or odd, and those two categories cover all integers with no overlap. So two cases, even $n$ and odd $n$, are exhaustive. That is the split the proof uses below.

Proof. Let $n$ be an arbitrary integer. Every integer is even or odd, which gives two exhaustive cases.

Case 1 ($n$ is even). Write $n = 2k$ for some integer $k$. Then

$$n^2 + n = (2k)^2 + 2k = 4k^2 + 2k = 2(2k^2 + k).$$

Since $2k^2 + k$ is an integer, $n^2 + n$ is $2$ times an integer, so it is even.

Case 2 ($n$ is odd). Write $n = 2k + 1$ for some integer $k$. Then

$$n^2 + n = (2k+1)^2 + (2k+1) = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1).$$

Since $2k^2 + 3k + 1$ is an integer, $n^2 + n$ is $2$ times an integer, so it is even.

Both cases give an even result, and the two cases cover every integer. Therefore $n^2 + n$ is even for every integer $n$. $\blacksquare$

One way to see the result without cases: $n^2 + n = n(n+1)$ is a product of two consecutive integers, and one of any two consecutive integers is even, so the product is even. The case proof and the consecutive-integer proof reach the same conclusion by different routes; a reader may prefer whichever makes the evenness most visible.

Existence Proofs

Some statements claim only that at least one object with a property exists. The symbol is $\exists x \, P(x)$.

The Official Definition

Constructive vs. nonconstructive existence proof (Rosen 8e, Section 1.8):

A proof of a proposition of the form $\exists x \, P(x)$ is called an existence proof. An existence proof is constructive if it finds an element $a$, called a witness, for which $P(a)$ is true; it is nonconstructive if it does not find such an element but rather proves $\exists x \, P(x)$ in some other way, for example by contradiction.

Source: Rosen 8e, Section 1.8, subsection 1.8.3 Existence Proofs, p.103-104.

A constructive proof hands over an actual object and verifies the property on it. A nonconstructive proof shows that some object must exist without producing it, often by ruling out the alternative through contradiction. Both are valid; they differ in whether the reader walks away holding the object.

Worked Example: Constructive

Claim. There exists a positive integer that can be written as the sum of two perfect cubes in two different ways.

Constructive proof. The number $1729$ works:

$$1729 = 1^3 + 12^3 = 1 + 1728, \qquad 1729 = 9^3 + 10^3 = 729 + 1000.$$

Both equalities hold, and the pairs $\{1, 12\}$ and $\{9, 10\}$ are different, so $1729$ is a witness. The statement is true. $\blacksquare$

Worked Example: Nonconstructive

Claim. There exist two irrational numbers $x$ and $y$ such that $x^y$ is rational.

Nonconstructive proof. Consider the number $\sqrt{2}^{\,\sqrt{2}}$. It is either rational or irrational.

Case 1. If $\sqrt{2}^{\,\sqrt{2}}$ is rational, then take $x = y = \sqrt{2}$. Both are irrational, and $x^y = \sqrt{2}^{\,\sqrt{2}}$ is rational, so the claim holds.

Case 2. If $\sqrt{2}^{\,\sqrt{2}}$ is irrational, then take $x = \sqrt{2}^{\,\sqrt{2}}$ and $y = \sqrt{2}$. Both are irrational, and

$$x^y = \left(\sqrt{2}^{\,\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\,(\sqrt{2} \cdot \sqrt{2})} = \sqrt{2}^{\,2} = 2,$$

which is rational, so the claim holds.

In one of the two cases the claim is true, so the required pair exists. The argument never settles which case is the real one, so it never names the actual $x$ and $y$. The existence is established without a witness. $\blacksquare$

Uniqueness Proofs

Some statements claim that an object with a property exists and is the only one. Section 1.8.4 separates this into two obligations.

A uniqueness proof has two parts. Existence: show that some element $x$ with the property $P(x)$ exists. Uniqueness: show that if both $x$ and $y$ have the property, then $x = y$ (equivalently, no element other than $x$ has the property). Establishing only one part leaves the claim half-proved.

Worked Example: The Additive Inverse

Claim. For every real number $a$, there is a unique real number $r$ such that $a + r = 0$.

Existence. Take $r = -a$. Then $a + r = a + (-a) = 0$, so a value $r$ with the property exists.

Uniqueness. Suppose $r$ and $s$ are both real numbers with $a + r = 0$ and $a + s = 0$. Then $a + r = a + s$. Adding $-a$ to both sides gives $r = s$. So any two values with the property are equal.

Existence and uniqueness together show that exactly one such $r$ exists, namely $r = -a$. $\blacksquare$

Counterexamples

A statement of the form $\forall x \, P(x)$ claims the property holds for every member of the domain. A single failure destroys it.

The Official Definition

Counterexample (Rosen 8e, Section 1.8):

Given a statement of the form $\forall x \, P(x)$, a counterexample is a value of $x$ in the domain for which $P(x)$ is false. Finding a counterexample shows that the universally quantified statement is false.

Source: Rosen 8e, Section 1.8, subsection 1.8.5 Proof Strategies / Looking for Counterexamples, p.110-111 (consistent with the counterexample definition in Section 1.4, p.44).

To disprove a universal claim, produce one member of the domain on which the property fails and verify the failure. One counterexample is enough; there is no need to find more than one. The reverse does not hold: failing to find a counterexample after a few tries does not prove the statement, since the next untried value might still break it.

Worked Example: Disproving a Tempting Pattern

Claim to test. “Every positive integer is the sum of the squares of three integers.”

Predict first. Predict whether this is true, then look for a small value that resists being written as $a^2 + b^2 + c^2$.

Check your prediction

The claim is false, and $7$ is a counterexample. The squares not exceeding $7$ are $0, 1, 4$. Every sum of three of these (with repetition allowed) is $0, 1, 2, 3, 4, 5, 6, 8, 9$, and so on, but no choice gives $7$: the only way to reach $6$ is $4 + 1 + 1$, and adding any further square would overshoot or require a fourth term. Since $7$ cannot be written as the sum of three integer squares, the universal claim fails. One counterexample finishes the disproof.

Common Misconceptions

Common misconception

a single confirming example proves a universal statement. A statement of the form $\forall x \, P(x)$ ranges over the whole domain, which is often infinite, so checking one value (or several) leaves the rest unverified. Testing $n = 1, 2, 3$ on a claim about all integers shows the claim survives three tries, not that it holds for every integer. A pattern that holds for the first few cases can still fail later. In the squares example the claim is true for $n = 1$ through $6$, yet $n = 7$ breaks it. One example settles an existence claim ($\exists x \, P(x)$) and one counterexample settles a universal claim being false, but no finite list of examples proves a universal claim true.

Common misconception

a proof by cases is valid even if the cases miss some possibilities. The case split must be exhaustive: every member of the domain has to land in at least one case. If a proof of a claim about all integers handles only positive integers, then zero and the negative integers are never addressed, and the argument proves nothing about them. Before trusting a case proof, check that the listed cases together cover the entire domain. Splitting into even and odd, or into positive, zero, and negative, are common exhaustive splits; splitting into “small” and “large” without a precise boundary usually is not.

Practice Problems

Level 1 Name the Right Method

For each statement, name which method of this section fits its shape: proof by cases, constructive existence proof, uniqueness proof, or counterexample.

(a) “There is an even prime number.”

(b) “Every prime number is odd.”

Thought Process

Read the leading word of each statement. “There is” signals existence. “Every... is odd” is a universal claim that might be disproved by one case. A claim about all integers that splits on a property signals cases.

Show Answer

(a) Constructive existence proof: exhibit the witness $2$, which is even and prime.

(b) Counterexample: the prime $2$ is even, so the universal claim is false.

(c) Proof by cases: split into $n \ge 0$ and $n < 0$ (or even and odd), and show $n^2 \ge 0$ in each case.

Level 2 A Two-Case Proof

Prove by cases that for every integer $n$, the number $n^2$ leaves a remainder of $0$ or $1$ when divided by $4$. (Equivalently, $n^2$ is never of the form $4k + 2$ or $4k + 3$.)

Thought Process

Split on whether $n$ is even or odd. Square each form and read off the remainder when divided by $4$.

Show Answer

Let $n$ be an arbitrary integer. The two cases even and odd are exhaustive.

Case 1 ($n$ even). Write $n = 2k$. Then $n^2 = 4k^2$, which has remainder $0$ when divided by $4$.

Case 2 ($n$ odd). Write $n = 2k + 1$. Then

$$n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1,$$

which has remainder $1$ when divided by $4$.

Both cases give remainder $0$ or $1$, and the cases cover every integer. Therefore $n^2$ always leaves remainder $0$ or $1$ when divided by $4$.

Level 3 Construct a Witness

Give a constructive existence proof that there is a positive integer equal to the sum of all the positive integers strictly less than it. (Such a number is called a perfect number with respect to this restricted sum.)

Thought Process

The claim asks for one number $m$ with $m = $ the sum of every positive integer below $m$. Test small numbers: for $m = 3$ the integers below it are $1$ and $2$, whose sum is $3$. Check whether that witness works.

Show Answer

Witness: $m = 3$. The positive integers strictly less than $3$ are $1$ and $2$, and $1 + 2 = 3 = m$. So $3$ equals the sum of all positive integers below it.

Because a specific witness has been exhibited and verified, the existence claim is true. The proof is constructive: it names the object rather than only arguing that one must exist.

(One way to see why no second witness appears among small numbers: for $m = 4$ the sum below is $1 + 2 + 3 = 6 \neq 4$, and the gap only grows for larger $m$.)

Level 4 Existence and Uniqueness Together

Prove that for every pair of real numbers $a$ and $b$ with $a \neq 0$, there is a unique real number $x$ such that $ax + b = 0$.

Thought Process

Two obligations. Existence: produce an $x$ that solves $ax + b = 0$. Uniqueness: assume two solutions $x$ and $y$ and force them to be equal. The condition $a \neq 0$ is what allows division.

Show Answer

Existence. Take $x = -\dfrac{b}{a}$, which is defined because $a \neq 0$. Then

$$ax + b = a\left(-\frac{b}{a}\right) + b = -b + b = 0,$$

so a solution exists.

Uniqueness. Suppose $x$ and $y$ both satisfy the equation, so $ax + b = 0$ and $ay + b = 0$. Subtracting gives $ax - ay = 0$, that is $a(x - y) = 0$. Since $a \neq 0$, dividing by $a$ gives $x - y = 0$, so $x = y$. Any two solutions are equal.

Existence and uniqueness together show there is exactly one solution, namely $x = -\dfrac{b}{a}$.

Level 5 Disprove or Prove

Decide whether each statement is true. If it is false, give a counterexample and verify it. If it is true, give a short proof.

(a) “For every pair of irrational numbers $x$ and $y$, the sum $x + y$ is irrational.”

(b) “For every integer $n$, if $n^2$ is even then $n$ is even.”

Thought Process

For (a), look for two irrationals whose sum collapses to a rational. For (b), the claim is a conditional inside a universal; a counterexample would need $n^2$ even but $n$ odd. Test whether an odd $n$ can ever produce an even square.

Show Answer

(a) False. Counterexample: $x = \sqrt{2}$ and $y = -\sqrt{2}$ are both irrational, yet $x + y = 0$, which is rational. The single pair $(\sqrt{2}, -\sqrt{2})$ breaks the universal claim, so the statement is false.

(b) True. Argue by contraposition: show that if $n$ is odd then $n^2$ is odd. Suppose $n$ is odd, so $n = 2k + 1$. Then

$$n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1,$$

which is odd. So an odd $n$ never gives an even $n^2$, which means an even $n^2$ forces an even $n$. No counterexample exists, and the statement is true.

(The contrast between the two parts is the point: a universal claim is disproved by one counterexample, but proved only by an argument covering the whole domain.)

Mastery Checklist

Novice (Level 1-2):

I can read the shape of a statement and name a fitting method (cases, existence, uniqueness, counterexample)
I can state the requirement that a case split be exhaustive
I can carry out a two-case proof on even and odd integers

Competent (Level 3-4):

I can give a constructive existence proof by exhibiting and verifying a witness
I can explain the difference between a constructive and a nonconstructive existence proof
I can write a uniqueness proof with its two separate parts, existence and uniqueness

Proficient (Level 5):

I can disprove a universal statement with a single verified counterexample
I can decide which statements need a full proof and which fall to one counterexample
I can explain why a finite list of confirming examples never proves a universal claim

Mental Model

The “shape first, then tool” picture:

Treat the first words of a claim as a label that names the tool. “For all... “ with a property that might fail says: hunt for one counterexample first; only if none turns up, prove it for the whole domain. “There exists... “ says: try to build a witness, and if building one resists, argue by contradiction that some object must exist anyway. “There is a unique... “ says: do two jobs, find one and rule out a second. A hypothesis that splits into separate situations says: handle each situation, and check the situations cover everything.

The matching habit keeps a proof from starting in the wrong direction. A reader who tries to “construct” a counterexample to a true universal statement, or who proves only existence when uniqueness was also required, has read the shape wrong, not done the algebra wrong.

Connections

Looking back:

Introduction to Proofs supplies the direct proof, proof by contraposition, and proof by contradiction that the methods here build on; the contraposition used in Level 5(b) and the contradiction used in nonconstructive existence both come from there.

Looking ahead:

Mathematical Induction is a structured proof method for statements about all positive integers, with a basis case and an inductive step that echo the disciplined case-splitting practiced here.
Sets proves identities such as $A \cup B = B \cup A$ by showing two inclusions, a natural use of two cases.
Functions proves a function one-to-one or onto using the existence and uniqueness arguments built here.

Real-world connections:

A safety argument that a system never reaches a bad state is a universal claim, so a single reachable bad state is a counterexample, the same role a counterexample plays in mathematics.
A constructive existence proof corresponds to an algorithm that returns an actual object, while a nonconstructive proof only certifies that an object exists, which matters when a program is supposed to produce the object and not merely confirm it can exist.

Resources

Resource	Where it points
Rosen 8e, Section 1.8 Proof Methods and Strategy (p.96-120, cases, existence, uniqueness, counterexamples)	Rosen, Discrete Mathematics and Its Applications, 8th ed., Sec. 1.8
Levin, Discrete Mathematics: An Open Introduction (open companion), Proofs and Proof Strategies	https://discrete.openmathbooks.org/dmoi3/sec_intro-proofs.html
Existing tree node: Mathematical Induction (Chapter 5, a major method this section sets up)	math301/ch5-sec1/mathematical-induction.md

Previous	Up	Next
Introduction to Proofs	Skills Index	Mathematical Induction

Last updated: 2026-06-16