Chapter 28 — Prove It
Table of Contents
28.1 Vocabulary of Proof
Key Terms:
| Term | Meaning | |—|—| | Distinct | Different from each other | | WLOG | “Without loss of generality” — assume a specific case that covers all possibilities by symmetry | | Trivial | Obvious or immediate (no deep argument needed) | | Lemma | A small theorem proved as a stepping-stone to a larger result | | Rigorous | A proof with no logical gaps | | If and only if (iff) | Both directions hold: $P \Rightarrow Q$ and $Q \Rightarrow P$ | | Necessary condition | $Q$ is necessary for $P$ means $P \Rightarrow Q$ | | Sufficient condition | $P$ is sufficient for $Q$ means $P \Rightarrow Q$ | | QED / $\square$ | Marks the end of a proof |
“If and only if” requires proving two directions:
- Forward: If $P$, then $Q$.
- Backward: If $Q$, then $P$.
Example: “$n^2$ is even if and only if $n$ is even.” You must prove both: (i) $n$ even $\Rightarrow$ $n^2$ even, and (ii) $n^2$ even $\Rightarrow$ $n$ even.
28.2 Direct Proof
A direct proof starts from known truths (axioms, definitions, previously proven results) and chains logical steps to reach the conclusion.
Example 28-1. Prove that the sum of two even integers is even.
Proof. Let $a = 2m$ and $b = 2n$ for integers $m, n$. Then:
\[a + b = 2m + 2n = 2(m + n).\]Since $m + n$ is an integer, $a + b$ is even. $\square$
Example 28-2. Prove that the product of two odd integers is odd.
Proof. Let $a = 2m + 1$ and $b = 2n + 1$. Then:
\[ab = (2m+1)(2n+1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1.\]Since $2mn + m + n$ is an integer, $ab$ is odd. $\square$
Exercise 28-1. Prove that the sum of an even and an odd integer is odd.
Exercise 28-2. Prove that for any integer $n$, $n^2 + n$ is always even.
28.3 Proof by Contradiction
Proof by contradiction (reductio ad absurdum): Assume the opposite of what you want to prove. Show this assumption leads to a logical contradiction. Therefore the original statement must be true.
Example 28-3. Prove that $\sqrt{2}$ is irrational.
Proof. Assume for contradiction that $\sqrt{2} = \dfrac{p}{q}$ where $p, q$ are integers with no common factor.
Then $2 = \dfrac{p^2}{q^2}$, so $p^2 = 2q^2$. This means $p^2$ is even, so $p$ is even (by contrapositive: if $p$ is odd, $p^2$ is odd).
Write $p = 2k$. Then $(2k)^2 = 2q^2$, so $4k^2 = 2q^2$, hence $q^2 = 2k^2$. So $q^2$ is even, meaning $q$ is even.
But then $p$ and $q$ are both even — contradicting our assumption that they share no common factor. $\square$
Example 28-4. Prove there are infinitely many primes.
Proof. Assume for contradiction there are finitely many primes: $p_1, p_2, \ldots, p_n$. Consider $N = p_1 p_2 \cdots p_n + 1$. Then $N$ is not divisible by any $p_i$ (remainder 1 when divided by each). So $N$ is either prime itself or divisible by a prime not on our list. Either way, our list was incomplete. Contradiction. $\square$
Exercise 28-3. Prove by contradiction that $\sqrt{3}$ is irrational.
28.4 Converse, Inverse, Contrapositive
Given a statement “If $P$, then $Q$” ($P \Rightarrow Q$):
| Name | Statement | Equivalent to original? | |—|—|—| | Original | $P \Rightarrow Q$ | — | | Converse | $Q \Rightarrow P$ | No (independent) | | Inverse | $\neg P \Rightarrow \neg Q$ | No (= converse) | | Contrapositive | $\neg Q \Rightarrow \neg P$ | Yes (always equivalent) |
Example. Original: “If it’s raining, the ground is wet.”
- Converse: “If the ground is wet, it’s raining.” (Not necessarily true — sprinklers?)
- Inverse: “If it’s not raining, the ground is not wet.” (Same as converse — not necessarily true.)
- Contrapositive: “If the ground is not wet, it’s not raining.” (Must be true.)
Proof by Contrapositive. Instead of proving $P \Rightarrow Q$ directly, you can prove $\neg Q \Rightarrow \neg P$. This is a valid proof technique since the contrapositive is logically equivalent to the original.
Example: “If $n^2$ is even, then $n$ is even.” Contrapositive: “If $n$ is odd, then $n^2$ is odd.” The contrapositive is easier to prove directly.
Exercise 28-4. State the converse, inverse, and contrapositive of: “If $x > 5$, then $x^2 > 25$.” Which are true?
28.5 Mathematical Induction
Principle of Mathematical Induction. To prove a statement $P(n)$ holds for all integers $n \geq n_0$:
- Base case: Prove $P(n_0)$ is true.
- Inductive step: Prove that $P(k) \Rightarrow P(k+1)$ for an arbitrary $k \geq n_0$.
Then $P(n)$ holds for all $n \geq n_0$.
Analogy: Induction is like dominoes. The base case knocks over the first domino. The inductive step shows that each domino knocks over the next. Therefore all dominoes fall.
Example 28-5. Prove that $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for all $n \geq 1$.
Base case ($n = 1$): LHS = $1$, RHS = $\frac{1 \cdot 2}{2} = 1$. ✓
Inductive step: Assume $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ (inductive hypothesis).
Then:
\[1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.\]This is the formula with $n = k+1$. ✓
By induction, the formula holds for all $n \geq 1$. $\square$
Example 28-6. Prove that $n! > 2^n$ for all $n \geq 4$.
Base case ($n = 4$): $4! = 24 > 16 = 2^4$. ✓
Inductive step: Assume $k! > 2^k$ for some $k \geq 4$. Then:
\[(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k \geq 2 \cdot 2^k = 2^{k+1}\](since $k + 1 \geq 5 > 2$). ✓ $\square$
Warning — Both steps are essential!
Without the base case: “Prove all horses are the same color” — the inductive step works for $n \geq 2$ but the base case for $n = 2$ fails.
Without the inductive step: Just checking a few cases doesn’t prove the statement for all $n$.
Exercise 28-5. Prove by induction: $1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$.
Exercise 28-6. Prove by induction: $2^n > n$ for all $n \geq 1$.
Exercise 28-7. Prove by induction that $n^3 - n$ is divisible by 6 for all $n \geq 1$.
28.6 The Pigeonhole Principle
Pigeonhole Principle. If $n + 1$ (or more) objects are placed into $n$ boxes, then at least one box contains at least 2 objects.
General Form. If $kn + 1$ objects are placed into $n$ boxes, then at least one box contains at least $k + 1$ objects.
Example 28-7. In a group of 13 people, at least two share the same birth month.
There are 12 months (boxes) and 13 people (objects). By the Pigeonhole Principle, at least one month has $\geq 2$ people. $\square$
Example 28-8. Among any 5 integers, some two have the same remainder when divided by 4.
There are 4 possible remainders: $0, 1, 2, 3$. With 5 integers and 4 boxes, at least two share a remainder. $\square$
Example 28-9. In a drawer of 5 red and 7 blue socks, how many must you pick (in the dark) to guarantee a matching pair?
There are 2 colors (boxes). To guarantee a pair, pick $2 + 1 = 3$ socks. $\square$
Exercise 28-8. Among 6 people, prove that either at least 3 mutually know each other, or at least 3 are mutual strangers. (Hint: Consider one person’s relationships.)
Exercise 28-9. Prove that among any 10 integers, some subset has a sum divisible by 10.
28.7 Fallacies and Common Mistakes
Fallacy 1 — Circular Reasoning. Using the conclusion as a step in its own proof.
Example (WRONG): “Prove $a = b$. From $a = b$, we get $a - b = 0$, which is $0 = 0$. ✓ So $a = b$.”
The error: we assumed $a = b$ to prove $a = b$.
Fallacy 2 — A Pattern Is Not a Proof.
$f(n) = n^2 + n + 41$ gives primes for $n = 0, 1, 2, \ldots, 39$, but $f(40) = 40^2 + 40 + 41 = 41^2$ is not prime.
Checking finitely many cases does not prove a statement for all $n$.
Fallacy 3 — Hidden Division by Zero.
“Proof” that $1 = 2$: Let $a = b$. Then $a^2 = ab$, so $a^2 - b^2 = ab - b^2$, i.e. $(a-b)(a+b) = b(a-b)$. Divide by $a - b$: $a + b = b$, so $2b = b$, hence $2 = 1$.
The error: dividing by $a - b = 0$.
Fallacy 4 — Square Root Sign Errors.
$\sqrt{x^2} = |x|$, not $x$. Forgetting absolute values can lead to false conclusions, e.g., “proving” $-1 = 1$.
Exercise 28-10. Find the error in each “proof”:
(a) $-1 = (-1)^1 = (-1)^{2/2} = ((-1)^2)^{1/2} = 1^{1/2} = 1$, so $-1 = 1$.
(b) Let $x = 1 + 2 + 4 + 8 + \cdots$. Then $x = 1 + 2(1 + 2 + 4 + \cdots) = 1 + 2x$, so $x = -1$. Hence $1 + 2 + 4 + 8 + \cdots = -1$.
The Big Picture — The Beauty of Proof
Why do we prove things? Because patterns can deceive. Mathematics demands certainty, and proof is the mechanism for achieving it.
The young Gauss amazed his teacher by instantly summing $1 + 2 + 3 + \cdots + 100 = 5050$ — not by adding sequentially, but by pairing: $(1 + 100) + (2 + 99) + \cdots = 50 \times 101$. This is the essence of mathematical thinking: insight followed by rigorous justification.
As you learn more mathematics, proof techniques become not just requirements but creative tools.
Problems to Solve for Chapter 28
Problem 508. Prove that the sum of three consecutive integers is always divisible by 3.
Problem 509. Prove by induction: $1 + 3 + 5 + \cdots + (2n-1) = n^2$.
Problem 510. Prove that $\sqrt{5}$ is irrational.
Problem 511. Prove by induction that $\displaystyle\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$.
Problem 512. The statement “If $n^2$ is divisible by 3, then $n$ is divisible by 3” — prove it by contrapositive.
Problem 513. Among 25 people, prove that some two were born in the same month. (Pigeonhole)
Problem 514. Prove that in any group of 6 people, there exist 3 who mutually know each other or 3 who are mutually strangers. (AHSME)
Problem 515. Prove by induction: $1 \cdot 1! + 2 \cdot 2! + \cdots + n \cdot n! = (n+1)! - 1$.
Problem 516. State the converse of: “If $x > 0$ and $y > 0$, then $xy > 0$.” Is the converse true?
Problem 517. Prove or disprove: “If $a + b$ is even and $b + c$ is even, then $a + c$ is even.”
Problem 518. Prove by induction that $7^n - 1$ is divisible by 6 for all $n \geq 1$.
Problem 519. If 5 points are placed inside a unit square, prove that some two are within $\frac{\sqrt{2}}{2}$ of each other. (Pigeonhole)
Problem 520. Find the error: “All positive integers are equal.” Proof by (flawed) induction: Base case ($n=1$): In a set of 1 integer, all are equal. Inductive step: Assume any set of $k$ integers are equal. Given $k+1$ integers $a_1, \ldots, a_{k+1}$: by hypothesis ${a_1, \ldots, a_k}$ are all equal, and ${a_2, \ldots, a_{k+1}}$ are all equal. So all $k+1$ are equal.
Problem 521. Prove that $n^2 + 1 \geq 2n$ for all positive integers $n$. (Two methods: direct and induction.)
Problem 522. Prove that between any two rational numbers there is another rational number (the rationals are dense).
Problem 523. Prove by induction: A set of $n$ elements has $2^n$ subsets.
Problem 524. Among any 52 integers, prove that some two have the property that their difference is divisible by 51.
Problem 525. Prove that $\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n(n+1)} = \dfrac{n}{n+1}$ by induction and verify by telescoping.