3.2 Direct Proof, Cases, and Contraposition

Section 3.1 separated examples from proof. A proof must handle an arbitrary object, not just selected values. We now study three proof strategies for universal implications:

Each strategy proves the same kind of claim but chooses a different route:

• direct proof starts with $P(x)$ and moves forward to $Q(x)$;

• proof by cases divides all possibilities into manageable branches;

• proof by contraposition proves $\neg Q(x)\to\neg P(x)$ instead.

Anatomy of a direct proof

A direct proof of $P\to Q$ assumes the hypothesis $P$ for an arbitrary object and uses definitions and known facts until the conclusion $Q$ follows.

The word “assume” here does not mean guessing that the theorem is true. Inside an implication, we are allowed to study the worlds in which the hypothesis holds. We must then prove that the conclusion also holds in every such world.

A reusable direct-proof structure is:

1. Let $x$ be an arbitrary object in the stated domain.

2. Assume the hypothesis $P(x)$.

3. Unpack definitions into usable mathematical forms.

4. Transform those forms through justified steps.

5. Match the result to the definition of $Q(x)$.

6. State the conclusion.

Worked proof: even plus odd is odd

Theorem. If $a$ is even and $b$ is odd, then $a+b$ is odd.

Start with arbitrary integers $a$ and $b$ satisfying the hypothesis.

Because $a$ is even, the definition gives an integer $r$ such that

Because $b$ is odd, there is an integer $s$ such that

Add the expressions:

Since integers are closed under addition, $r+s$ is an integer. The final expression has the form $2k+1$ with integer $k=r+s$. By the definition of odd, $a+b$ is odd.

Notice the proof’s direction:

Every sentence has a job. Merely writing $a+b$ is odd would repeat the conclusion rather than justify it.

Build the proof bridge in dependency order. The algebraic substitution cannot appear before the even and odd definitions introduce $r$ and $s$. The final step must also explain why $r+s$ is an integer, because the odd-number definition requires an integer witness.

Proof by cases divides an exhaustive domain

Sometimes one forward argument does not fit every possible object. A proof by cases partitions the domain into branches, proves the conclusion in each branch, and then combines them.

Valid cases must satisfy two requirements:

• exhaustive: every possible object belongs to at least one case;

• manageable overlap: overlapping cases are allowed, but every overlap must still be covered consistently. Disjoint cases are often easier.

For integers, “even” and “odd” form an exhaustive, disjoint pair: every integer belongs to exactly one branch.

Worked proof by parity cases

Theorem. For every integer $n$, the product $n(n+1)$ is even.

We split into two cases.

Case 1: $n$ is even. Then $n=2k$ for some integer $k$. Therefore

which is even because $k(n+1)$ is an integer.

Case 2: $n$ is odd. Then $n=2k+1$ for some integer $k$, so

Thus

which is even.

The cases cover every integer, and the conclusion holds in both. Therefore $n(n+1)$ is even for every integer $n$.

A common mistake is choosing cases that omit a boundary. For a real number $x$, the cases $x<0$ and $x>0$ omit $x=0$. Use $x<0$ and $x\ge0$, or use three cases $x<0$, $x=0$, $x>0$.

Contraposition reverses and negates the route

Chapter 2 established the logical equivalence

The expression $\neg Q\to\neg P$ is the contrapositive of $P\to Q$. A proof by contraposition proves the contrapositive instead of the original implication.

This strategy is useful when the negation of the conclusion provides a concrete form that is easier to manipulate.

Worked proof: an even square comes from an even integer

Theorem. If $n^2$ is even, then $n$ is even.

A direct proof would begin with $n^2=2k$ and try to extract a factor of $2$ from $n$. That requires more divisibility machinery than we currently have. The contrapositive is simpler:

> If $n$ is not even, then $n^2$ is not even.

Every integer that is not even is odd. Let

for some integer $k$. Then

The value $2k^2+2k$ is an integer, so $n^2$ is odd and therefore not even. We have proved the contrapositive. Because the contrapositive is logically equivalent to the original implication, the theorem follows.

First verify that even and odd cases cover every integer in the switchyard. Then enter the squaring tunnel: the numeric samples illustrate the pattern, while the symbolic form $(2k+1)^2=2(2k^2+2k)+1$ supplies the general contrapositive proof.

How to choose among the strategies

Start by writing the hypothesis and conclusion explicitly. Then inspect their definitions:

This table is guidance, not an automatic rule. More than one strategy may work. A strong proof writer tries the route that makes the definitions easiest to use and the logical obligations easiest to see.

Do not confuse contraposition with the converse. From $P\to Q$, the contrapositive is $\neg Q\to\neg P$ and is equivalent. The converse $Q\to P$ is a different claim and may be false.

Bridge to the next section

Direct proof, cases, and contraposition all establish a conclusion through forward implications. Some claims are easier when we temporarily assume their negation and show that this assumption is impossible. Section 3.3 develops proof by contradiction, then separates the tasks of proving existence and proving uniqueness.