Standard proof methods

This chapter introduces fundamental proof techniques essential for constructing rigorous mathematical arguments. Mastery of direct proof, contrapositive proof, proof by contradiction, and proof by cases is critical for success in advanced logic and discrete mathematics examinations. These methods form the bedrock of mathematical reasoning and problem-solving.

---

Chapter Contents

|

| Topic |

|---|-------| | 1 | Direct proof | | 2 | Contrapositive proof | | 3 | Proof by contradiction | | 4 | Proof by cases |

---

We begin with Direct proof.

Part 1: Direct proof

Direct Proof

Overview

Direct proof is the most basic and most important proof method. To prove a statement of the form “if $P$, then $Q$”, we assume $P$ and logically derive $Q$. Even in advanced mathematics, a large number of proofs are still direct proofs in disguise. ---

Learning Objectives

---

Core Idea

---

Standard Direct-Proof Templates

---

Minimal Worked Examples

Example 1 Prove directly: if $n$ is even, then $n^2$ is even. Assume $n$ is even. Then $\qquad n=2k$ for some integer $k$. So $\qquad n^2=(2k)^2=4k^2=2(2k^2)$ Since $2k^2$ is an integer, $n^2$ is even. --- Example 2 Prove directly: if $a$ and $b$ are divisible by $3$, then $a+b$ is divisible by $3$. Assume $\qquad a=3m,\quad b=3n$ for integers $m,n$. Then $\qquad a+b=3m+3n=3(m+n)$ Since $m+n$ is an integer, $a+b$ is divisible by $3$. ---

How Definitions Drive the Proof

---

Common Mistakes

---

When Direct Proof Is Best

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="To prove directly that an integer $n$ is even, the most standard form to write is" options=["$n=2k$ for some integer $k$","$n=2k+1$ for some integer $k$","$n=k^2$ for some integer $k$","$n=3k$ for some integer $k$"] answer="A" hint="Use the definition of evenness." solution="An integer is even exactly when it can be written as $\qquad n=2k$ for some integer $k$. Therefore the correct option is $\boxed{A}$." ::: :::question type="NAT" question="If $n=2k+1$ is odd, then $n+1$ is divisible by what positive integer?" answer="2" hint="Use the form of an odd integer." solution="If $\qquad n=2k+1$, then $\qquad n+1=2k+2=2(k+1)$. Hence $n+1$ is divisible by $\boxed{2}$." ::: :::question type="MSQ" question="Which of the following are standard direct-proof moves?" options=["Assume the hypothesis","Use the relevant definition","Derive the conclusion logically","Assume the conclusion first and declare the proof finished"] answer="A,B,C" hint="Think of the normal structure of a direct proof." solution="In a direct proof, we assume the hypothesis, use definitions, and derive the conclusion. Assuming the conclusion without justification is invalid. Hence the correct answer is $\boxed{A,B,C}$." ::: :::question type="SUB" question="Prove directly that if an integer $n$ is divisible by $4$, then $n^2$ is divisible by $16$." answer="If $n=4k$, then $n^2=16k^2$." hint="Start from the definition of divisibility by $4$." solution="Assume $n$ is divisible by $4$. Then there exists an integer $k$ such that $\qquad n=4k$. Squaring, $\qquad n^2=(4k)^2=16k^2$. Since $k^2$ is an integer, $n^2$ is divisible by $16$. Hence the statement is proved." ::: ---

Summary

---

---

Part 2: Contrapositive proof

Contrapositive Proof

Overview

Contrapositive proof is one of the cleanest methods for proving implications. Instead of proving $\qquad P \implies Q$ directly, we prove the logically equivalent statement $\qquad \neg Q \implies \neg P$ This method is especially powerful in problems involving divisibility, parity, inequalities, and set inclusion, where the negation of the conclusion has a more workable algebraic form. ---

Learning Objectives

---

Core Idea

---

Why This Method Works

---

When to Use Contrapositive

---

Standard Structure

---

Minimal Worked Examples

Example 1 Prove: If an integer $n$ is divisible by $4$, then $n$ is even. A direct proof is easy, but the contrapositive is also simple: Contrapositive: If $n$ is not even, then $n$ is not divisible by $4$. If $n$ is not even, then $n$ is odd. An odd number cannot be divisible by $4$. Hence the contrapositive is true, so the original statement is true. --- Example 2 Prove: If $n^2$ is odd, then $n$ is odd. Contrapositive: If $n$ is not odd, then $n$ is even. Let $n=2k$. Then $\qquad n^2 = (2k)^2 = 4k^2 = 2(2k^2)$ so $n^2$ is even. Thus the contrapositive is true, and therefore the original statement is true. ---

High-Value Patterns

---

Negation Practice

---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="The contrapositive of the statement 'If $n$ is divisible by $4$, then $n$ is even' is" options=["If $n$ is even, then $n$ is divisible by $4$","If $n$ is not divisible by $4$, then $n$ is not even","If $n$ is not even, then $n$ is not divisible by $4$","If $n$ is odd, then $n$ is divisible by $4$"] answer="C" hint="For $P \implies Q$, contrapositive is $\neg Q \implies \neg P$." solution="Here $\qquad P:$ '$n$ is divisible by $4$' and $\qquad Q:$ '$n$ is even'. So the contrapositive is $\qquad \neg Q \implies \neg P$, that is, $\qquad$ If $n$ is not even, then $n$ is not divisible by $4$. Hence the correct option is $\boxed{C}$." ::: :::question type="NAT" question="If $n$ is odd, then $n^2$ is odd. What is the correct proof method name if we instead prove 'if $n^2$ is even, then $n$ is even' and use that equivalence?" answer="contrapositive" hint="Think of the logically equivalent implication." solution="The method is called proof by contrapositive, because one proves the logically equivalent implication $\qquad \neg Q \implies \neg P$ instead of proving $\qquad P \implies Q$ directly. Hence the answer is $\boxed{\text{contrapositive}}$." ::: :::question type="MSQ" question="Which of the following statements are logically equivalent to $P \implies Q$?" options=["$\neg Q \implies \neg P$","$Q \implies P$","$\neg P \implies \neg Q$","$\neg(P \implies Q)$"] answer="A" hint="Only one standard implication is always equivalent." solution="The only implication that is always logically equivalent to $\qquad P \implies Q$ is its contrapositive $\qquad \neg Q \implies \neg P$. The converse $Q \implies P$ and inverse $\neg P \implies \neg Q$ are not generally equivalent. Hence the correct answer is $\boxed{A}$." ::: :::question type="SUB" question="Prove that if $n^2$ is odd for an integer $n$, then $n$ is odd." answer="True by contrapositive" hint="Prove instead that if $n$ is even, then $n^2$ is even." solution="We prove the contrapositive. Assume $n$ is even. Then for some integer $k$, $\qquad n=2k$. Hence $\qquad n^2=(2k)^2=4k^2=2(2k^2)$, which is even. So we have shown: $\qquad$ if $n$ is even, then $n^2$ is even. This is the contrapositive of the statement: $\qquad$ if $n^2$ is odd, then $n$ is odd. Therefore the original statement is true. Hence the answer is $\boxed{\text{True by contrapositive}}$." ::: ---

Summary

---

---

Part 3: Proof by contradiction

Proof by Contradiction

Overview

Proof by contradiction is a method in which one assumes the statement to be false and then derives an impossibility. The contradiction may be with the assumptions, with a known theorem, or with a basic fact such as parity or order. In CMI-style questions, contradiction is often used when no direct construction is visible, especially in number theory, irrationality, set theory, and existence statements. ---

Learning Objectives

---

Core Idea

---

Logical Structure

---

Contradiction vs Contrapositive

---

When Contradiction Is Natural

---

Minimal Worked Example

Example 1 Prove that $\sqrt{2}$ is irrational. Assume for contradiction that $\sqrt{2}$ is rational. Then $\qquad \sqrt{2} = \dfrac{a}{b}$ for integers $a,b$ with no common factor and $b\ne0$. Squaring gives $\qquad 2 = \dfrac{a^2}{b^2}$ so $\qquad a^2 = 2b^2$ Hence $a^2$ is even, so $a$ is even. Write $a=2k$. Then $\qquad a^2 = 4k^2 = 2b^2$ so $\qquad b^2 = 2k^2$ Hence $b^2$ is even, so $b$ is even. Thus both $a$ and $b$ are even, contradicting the assumption that $\dfrac{a}{b}$ was in lowest terms. Therefore $\sqrt{2}$ is irrational. ---

Valid Forms of Contradiction

---

How to Recognize a Good Contradiction

---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="To prove a statement $P$ by contradiction, the first step is to assume" options=["$P$","$\neg P$","both $P$ and $\neg P$","a weaker version of $P$"] answer="B" hint="Contradiction starts by negating what you want to prove." solution="In proof by contradiction, one assumes the negation of the desired statement and then derives an impossibility. Therefore the correct first step is to assume $\neg P$. Hence the correct option is $\boxed{B}$." ::: :::question type="NAT" question="In the classical proof that $\sqrt{2}$ is irrational, if $a^2=2b^2$, what can you conclude about $a$?" answer="even" hint="If $a^2$ is even, then $a$ is even." solution="Since $\qquad a^2 = 2b^2$, the number $a^2$ is even. Therefore $a$ must be even. Hence the answer is $\boxed{\text{even}}$." ::: :::question type="MSQ" question="Which of the following are standard uses of proof by contradiction?" options=["Proving irrationality","Proving impossibility","Proving uniqueness","Showing a statement by checking only one example"] answer="A,B,C" hint="Contradiction is often used when direct construction is hard." solution="1. True. Irrationality proofs often use contradiction.

True. Contradiction is a standard tool for impossibility proofs.

True. Uniqueness is often shown by assuming two distinct such objects exist and deriving a contradiction.

False. One example never proves a general statement.

Hence the correct answer is $\boxed{A,B,C}$." ::: :::question type="SUB" question="Prove that $\sqrt{2}$ is irrational." answer="True by contradiction" hint="Assume $\sqrt{2}=\dfrac{a}{b}$ in lowest terms." solution="Assume for contradiction that $\sqrt{2}$ is rational. Then there exist integers $a,b$ with no common factor and $b\ne0$ such that $\qquad \sqrt{2}=\dfrac{a}{b}$. Squaring both sides gives $\qquad 2=\dfrac{a^2}{b^2}$, so $\qquad a^2=2b^2$. Thus $a^2$ is even, and therefore $a$ is even. Write $\qquad a=2k$. Then $\qquad a^2=4k^2$, so from $a^2=2b^2$ we get $\qquad 4k^2=2b^2$, hence $\qquad b^2=2k^2$. Thus $b^2$ is even, so $b$ is even. Therefore both $a$ and $b$ are even, which contradicts the assumption that $a$ and $b$ had no common factor. Hence our assumption was false, and $\sqrt{2}$ is irrational. Therefore the answer is $\boxed{\text{True by contradiction}}$." ::: ---

Summary

---

---

Part 4: Proof by cases

Proof by Cases

Overview

Proof by cases is a method in which the problem is split into several possibilities, and the statement is proved separately in each one. This method is useful when the object naturally falls into disjoint categories, such as even or odd integers, positive or negative real numbers, or geometric configurations with distinct structures. ---

Learning Objectives

---

Core Idea

---

When to Use Cases

---

Standard Structure

---

What Makes a Good Case Split

---

Minimal Worked Examples

Example 1 Prove that for every integer $n$, the product $n(n+1)$ is even. Case 1: $n$ is even. Then $n(n+1)$ is even. Case 2: $n$ is odd. Then $n+1$ is even, so $n(n+1)$ is even. Hence in both cases $n(n+1)$ is even. --- Example 2 Prove that for every real number $x$, $\qquad |x| \ge x$ Case 1: $x\ge0$. Then $|x|=x$, so $|x|\ge x$. Case 2: $x<0$. Then $|x|=-x$, and since $-x>x$, we again have $|x|\ge x$. Thus the statement is true in all cases. ---

High-Value Case Splits

---

Choosing the Right Cases

For example, if a statement is about parity, do not split into positive and negative cases first. ---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="To prove that $n(n+1)$ is even for every integer $n$, the most natural case split is" options=["$n>0$ and $n<0$","$n$ even and $n$ odd","$n$ prime and $n$ composite","$n=0$ and $n\ne0$"] answer="B" hint="The statement is about a product of consecutive integers." solution="The key structural fact is parity: every integer is either even or odd. One of $n$ and $n+1$ must therefore be even. So the most natural split is into the cases '$n$ even' and '$n$ odd'. Hence the correct option is $\boxed{B}$." ::: :::question type="NAT" question="How many cases are needed in the most natural proof by cases of the statement 'For every integer $n$, $n(n+1)$ is even'?" answer="2" hint="Use parity." solution="The natural split is by parity: $\qquad n$ even or $n$ odd. So the proof requires $\boxed{2}$ cases." ::: :::question type="MSQ" question="Which of the following are good principles for proof by cases?" options=["The cases should cover all possibilities","The cases should help simplify the statement","It is acceptable to ignore a difficult case if the others work","The final conclusion should mention that all cases have been handled"] answer="A,B,D" hint="A case proof must be complete." solution="1. True. The cases must be exhaustive.

True. The split should make the argument easier.

False. Every case must be proved.

True. The proof should conclude that all cases are covered.

Hence the correct answer is $\boxed{A,B,D}$." ::: :::question type="SUB" question="Prove that for every integer $n$, the integer $n(n+1)$ is even." answer="True by parity cases" hint="Consider whether $n$ is even or odd." solution="We use proof by cases. Case 1: $n$ is even. Then $n=2k$ for some integer $k$, so $n(n+1)$ is divisible by $2$, hence even. Case 2: $n$ is odd. Then $n=2k+1$ for some integer $k$, so $\qquad n+1 = 2k+2 = 2(k+1)$, which is even. Hence the product $n(n+1)$ is even. Thus in both cases $n(n+1)$ is even. Therefore the statement is true. Hence the answer is $\boxed{\text{True by parity cases}}$." ::: ---

Summary

Chapter Summary

Chapter Review Questions

:::question type="MCQ" question="Consider the statement: 'For any integers $a$ and $b$, if $ab$ is an odd integer, then both $a$ and $b$ must be odd integers.' Which of the following proof strategies is generally considered the most straightforward and elegant for this statement?" options=["Direct proof, by assuming $ab = 2k+1$ and deducing $a=2m+1$ and $b=2n+1$.", "Proof by contrapositive, by assuming $a$ is even or $b$ is even, then showing $ab$ is even.", "Proof by contradiction, by assuming $ab$ is odd and ( $a$ is even or $b$ is even), then deriving a contradiction.", "Proof by cases, by considering all four parity combinations for $a$ and $b$ (even/even, even/odd, odd/even, odd/odd)."] answer="Proof by contrapositive, by assuming $a$ is even or $b$ is even, then showing $ab$ is even." hint="Consider which assumption (P or not Q) provides a simpler starting point for algebraic manipulation related to parity." solution="The contrapositive of the statement 'If $ab$ is odd, then $a$ is odd and $b$ is odd' is 'If $a$ is even or $b$ is even, then $ab$ is even'. This is easier to prove directly: If $a$ is even, $a=2k$, so $ab=2kb$, which is even. If $b$ is even, $b=2k$, so $ab=a(2k)$, which is even. Thus, if either $a$ or $b$ is even, $ab$ is even. This makes the contrapositive proof very direct and elegant. While contradiction also works, contrapositive is more direct."
:::

:::question type="NAT" question="To prove that for any integer $n$, the expression $n^3 - n$ is divisible by 6, one common approach is to use proof by cases based on the value of $n$ modulo $k$. What is the smallest positive integer $k$ such that considering $n$ modulo $k$ naturally covers all necessary cases without redundancy for divisibility by 6?" answer="6" hint="Consider the prime factors of 6 and how they relate to consecutive integers." solution="The expression $n^3 - n$ can be factored as $n(n^2 - 1) = n(n-1)(n+1)$. This is a product of three consecutive integers. Among any three consecutive integers, at least one is even (divisible by 2) and exactly one is divisible by 3. Therefore, their product must be divisible by $2 \times 3 = 6$. While this specific problem has a more elegant algebraic solution, if one were to use proof by cases, considering $n$ modulo 6 (i.e., $n \equiv 0, 1, 2, 3, 4, 5 \pmod{6}$) would naturally cover all cases for divisibility by 6. Thus, $k=6$ is the smallest such integer."
:::

:::question type="MCQ" question="Consider the statement: 'The sum of a rational number and an irrational number is always irrational.' If you are to prove this statement using proof by contradiction, which of the following represents the correct initial assumption?" options=["Assume the sum of a rational and an irrational number is rational.", "Assume the sum of two irrational numbers is rational.", "Assume the sum of two rational numbers is irrational.", "Assume the sum of a rational and an irrational number is irrational, then seek a contradiction."] answer="Assume the sum of a rational and an irrational number is rational." hint="Proof by contradiction assumes the negation of the conclusion. What is the negation of 'is always irrational'?" solution="Let $x$ be rational and $y$ be irrational. The statement to prove is $x+y$ is irrational. For a proof by contradiction, we assume the negation of this conclusion while retaining the hypotheses. So, the initial assumption is that $x$ is rational, $y$ is irrational, AND $x+y$ is rational. This assumption will then lead to a contradiction (specifically, that $y = (x+y) - x$ would be rational, contradicting that $y$ is irrational)."
:::

What's Next?