Mathematical-Reasoning · Unit 9 · Video 1 · Interactive Practice

Proof by Cases: Why It Works, and Why n² + n Is Even

IKey Formulas

Statement	Name	What it gives a proof
$(P \lor Q) \to R \equiv (P \to R) \land (Q \to R)$	The case equivalence	Two separate proofs: assume $P$ and reach $R$ , then assume $Q$ and reach $R$
Every integer is even or odd	An exhaustive split	“ $n$ is an integer” says the same as “ $n$ is even or $n$ is odd”
$n = 2m$ or $n = 2m + 1$ , with $m \in \mathbb{Z}$	Definitions of even and odd	An equation to substitute in each case
$\neg(X \land Y) \equiv \neg X \lor \neg Y$	De Morgan’s law	Turns an “and” conclusion into an “or” hypothesis in the contrapositive

Key Insight: The “or” in the hypothesis becomes an “and” between two conditionals. Both cases must be proved, the cases must cover every possibility, and neither case may use the other’s assumption.

IIThe Truth Table Behind Proof by Cases

Only the conjunction $(P \to R) \land (Q \to R)$ matches $(P \lor Q) \to R$ in all eight rows.

Right side Row 4

IIITwo Cases for $n^2 + n$

Every integer falls in one of the two cases, and each case supplies its own equation and its own $m$ .

n 5

Case 1 (Proposition 2): $n$ is even

n = 2m

n^2 + n = (2m)^2 + 2m = 4m^2 + 2m = 2(2m^2 + m)

Case 2 (Proposition 3): $n$ is odd

n = 2m + 1

\begin{aligned} n^2 + n &= (2m+1)^2 + (2m+1) \\ &= 4m^2 + 6m + 2 \\ &= 2(2m^2 + 3m + 1) \end{aligned}

IVCases from De Morgan: When Is $xy$ Even?

The contrapositive’s hypothesis “ $x$ is even or $y$ is even” is the union of two cases; the points left over have $xy$ odd.

x 4 y 3

VQuiz Questions

Problem 1 · The Case Equivalence

Given: statements $P$ , $Q$ and $R$ . Which statement is logically equivalent to $(P \lor Q) \to R$ ?

✅ Correct! Both statements are false in exactly rows 2, 4 and 6 of the truth table, the rows where

P \lor Q

is true and

R

is false.

❌ Not quite. One conditional is not enough. When

P

is false,

Q

is true and

R

is false,

P \to R

is true but

(P \lor Q) \to R

is false.

❌ Not quite. This is the converse. When

P

and

Q

are false and

R

is true,

R \to (P \lor Q)

is false but

(P \lor Q) \to R

is true.

❌ Close, but… the connective between the conditionals must be “and”. When

P

is true and

Q

and

R

are false,

Q \to R

is true, so this “or” statement is true, while

(P \lor Q) \to R

is false.

Show solution

Rows in the order TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF for $P$ , $Q$ , $R$ :

Row	$(P \lor Q) \to R$	$P \to R$	$R \to (P \lor Q)$	$(P \to R) \land (Q \to R)$	$(P \to R) \lor (Q \to R)$
1	T	T	T	T	T
2	F	F	T	F	F
3	T	T	T	T	T
4	F	F	T	F	T
5	T	T	T	T	T
6	F	T	T	F	T
7	T	T	F	T	T
8	T	T	T	T	T

Only the column for $(P \to R) \land (Q \to R)$ matches the column for $(P \lor Q) \to R$ in every row, so the answer is c. The other three each differ in at least one row: $P \to R$ in row 6, the converse in rows 2, 4, 6 and 7, and the “or” statement in rows 4 and 6.

Problem 2 · Do the Cases Cover Everything?

Given: a proof of a statement about every integer $n$ splits into two cases. Which pair of cases does not give a valid proof by cases?

✅ Correct! The integer

n = 2

is neither a multiple of

4

nor odd, so it falls in no case, and the two proofs say nothing about it. The same goes for

6

10

-2

, and every even number that is not a multiple of

4

❌ Not quite. Every integer is even or odd, so these two cases cover every integer. This is the split used for

n^2 + n

❌ Not quite. Every integer

n

satisfies

n \geq 0

n < 0

, so these cases cover every integer.

❌ Not quite. These cases overlap at

3

4

and

5

, but every integer satisfies

n \leq 5

n \geq 3

. Cases must cover every possibility; they do not have to be separate, and an integer in both cases is covered by either proof.

Show solution

A proof by cases proves $(P \lor Q) \to R$ , so the disjunction $P \lor Q$ must hold for every integer the statement is about. Check each pair:

(a) Every integer is even or odd: covered.
(b) For $n = 2$ , “ $2$ is a multiple of $4$ ” is false and “ $2$ is odd” is false: not covered.
(c) Every integer is nonnegative or negative: covered.
(d) If $n \leq 5$ is false, then $n > 5$ , so $n \geq 3$ : covered.

So the invalid split is b.

Problem 3 · Case 2 with a Negative Odd Integer

Given: $n = -5$ , handled by Case 2 of the proof that $n^2 + n$ is even: write $n = 2m + 1$ , then $n^2 + n = 2(2m^2 + 3m + 1)$ . Find $m$ and the integer $2m^2 + 3m + 1$ .

What is m?

What is 2m² + 3m + 1?

✅ Correct! With

m = -3

2m + 1 = -5

and

2m^2 + 3m + 1 = 10

, so

n^2 + n = 2 \cdot 10 = 20

, which is even.

❌ Check the sign.

m = -2

gives

2m + 1 = -3

, not

-5

. Solve

-5 = 2m + 1

m = \frac{-5 - 1}{2}

❌ Wrong case.

m = n/2

is the Case 1 formula, and here it is not an integer. For odd

n

the Case 2 equation gives

m = \frac{n - 1}{2}

❌ Not quite.

m = n - 1

forgets to halve. Check:

2(-6) + 1 = -11

, not

-5

❌ Not quite.

3

is what

m = -2

gives. With

m = -3

2(9) + 3(-3) + 1 = 18 - 9 + 1

❌ Not quite.

20

n^2 + n

itself. The integer inside the parentheses is half of it.

❌ Check the sign.

3m = 3(-3) = -9

, not

+9

, so the middle term subtracts.

Show solution

Since $-5$ is odd, write $-5 = 2m + 1$ . Then $2m = -6$ , so $m = -3$ , an integer.

2m^2 + 3m + 1 = 2(-3)^2 + 3(-3) + 1 = 18 - 9 + 1 = 10

Check directly: $n^2 + n = 25 + (-5) = 20 = 2 \cdot 10$ . So $m = -3$ and $2m^2 + 3m + 1 = 10$ .

Problem 4 · Plan a Proof by Cases

Given: the proposition “For all integers $a$ and $b$ , if $3 \nmid ab$ , then $3 \nmid a$ and $3 \nmid b$ .” Which plan is a complete proof?

✅ Correct! By De Morgan’s law the contrapositive is “if

3 \mid a

3 \mid b

, then

3 \mid ab

”, which has the form

(P \lor Q) \to R

. The two cases prove

P \to R

and

Q \to R

❌ Not quite. These cases try to prove a false statement: with

a = 1

and

b = 3

3 \nmid a

but

3 \mid ab

. The negations must go through the contrapositive, where they swap sides.

❌ Not quite. Assuming both

3 \mid a

and

3 \mid b

proves

(P \land Q) \to R

, which says nothing about

a = 3

b = 1

. The contrapositive needs an “or” in its hypothesis, so it needs two cases.

❌ Close, but… one conditional is not enough. This proves

P \to R

only, and leaves pairs such as

a = 1

b = 3

unproved; a second case,

3 \mid b

, is required.

Show solution

Contrapositive. Negating “ $3 \nmid a$ and $3 \nmid b$ ” gives, by De Morgan’s law, “ $3 \mid a$ or $3 \mid b$ ”. So the contrapositive is: if $3 \mid a$ or $3 \mid b$ , then $3 \mid ab$ . With $P$ : $3 \mid a$ , $Q$ : $3 \mid b$ , $R$ : $3 \mid ab$ , it has the form $(P \lor Q) \to R$ .

Case 1: $3 \mid a$ . Then $a = 3k$ for some integer $k$ , so $ab = 3(kb)$ , and $kb$ is an integer. Hence $3 \mid ab$ .

Case 2: $3 \mid b$ . Then $b = 3j$ for some integer $j$ , so $ab = 3(aj)$ , and $aj$ is an integer. Hence $3 \mid ab$ .

The two cases prove $(P \to R) \land (Q \to R) \equiv (P \lor Q) \to R$ , which is the contrapositive, and a conditional is equivalent to its contrapositive. So the plan is d.

Solved: 0 / 4

Proof by Cases: Why It Works, and Why n² + n Is Even

IKey Formulas

IIThe Truth Table Behind Proof by Cases

IIITwo Cases for n2+nn^2 + nn2+n

IVCases from De Morgan: When Is xyxyxy Even?

VQuiz Questions

IIITwo Cases for $n^2 + n$

IVCases from De Morgan: When Is $xy$ Even?