Direct proof, proof by contradiction, proof by induction.
Self-serve tutorial - low prerequisites, straightforward concepts.
In discrete math and CS, you’re rarely asked to “compute” something—you’re asked to justify why something is always true. Proof techniques are the reusable tools that turn an intuition (“this should work”) into a guarantee (“this must work”).
Direct proof builds the conclusion from assumptions step by step. Contradiction proves a statement by showing its negation would force an impossibility. Induction proves ∀n ∈ ℕ statements by (1) a base case and (2) showing n ⇒ n+1.
A proof is a finite sequence of logically valid steps that establishes a statement is true. In this node, “proof techniques” means a small toolkit of common patterns you can apply again and again:
Why do we need “techniques” at all? Because most statements you prove in discrete math and CS have recurring logical shapes. If you recognize the shape, you can choose a proof method that matches it.
Many statements you’ll prove look like one of these:
1) Implication: P ⇒ Q ("If P, then Q")
2) Universal claim: ∀x, S(x) ("For all x, S(x) holds")
Often these combine: ∀n ∈ ℕ, P(n) ⇒ Q(n).
A direct proof is usually the default for implications: assume P and derive Q.
A contradiction proof is useful when the statement is hard to build directly but easy to refute: assume ¬S and show that cannot happen.
Induction is specialized to universal claims over ℕ (or any well-ordered set where “next” makes sense).
In programming, the compiler checks correctness rules. In proofs, you must make each step justified. A good habit:
This pacing matters: it keeps proofs readable and prevents you from accidentally assuming what you’re trying to prove.
| Statement style | Typical goal | Good technique | Why |
|---|---|---|---|
| P ⇒ Q | Derive Q from P | Direct proof | Matches the structure |
| “No such x exists” / impossibility | Show contradiction emerges | Contradiction | Negation introduces an existence claim |
| ∀n ∈ ℕ, S(n) | Prove all n | Induction | Propagates truth along ℕ |
You can always force a statement into any technique (e.g., prove P ⇒ Q by contradiction), but choosing the “natural” one usually yields a cleaner proof.
Direct proof mirrors how we reason in code: if the input satisfies some precondition P, we show the output satisfies postcondition Q. This is exactly proving P ⇒ Q.
The key move is:
To prove: P ⇒ Q
1) Assume P.
2) Derive...
3) Therefore Q.
When proving a universal implication, you add one extra step:
To prove: ∀x, (P(x) ⇒ Q(x))
1) Let x be arbitrary.
2) Assume P(x).
3) Derive Q(x).
4) Conclude ∀x, (P(x) ⇒ Q(x)).
That “let x be arbitrary” is crucial: it prevents you from accidentally proving the statement only for a special case.
Definitions drive many direct proofs.
Direct proofs often look like: assume a definition, substitute, and simplify.
Claim: If n is even, then n² is even.
Assume n is even.
Then ∃k ∈ ℤ such that n = 2k.
Now compute:
n² = (2k)²
= 4k²
= 2(2k²)
Since 2k² ∈ ℤ, we have written n² as 2(integer), so n² is even.
Notice the structure:
Sometimes P ⇒ Q is true, but going forward from P doesn’t give you traction. Two common reasons:
1) Q is an impossibility / non-existence statement (e.g., “there is no integer solution”). Directly proving non-existence can be awkward.
2) The statement’s contrapositive is easier.
A useful related move (still “direct” in spirit) is proving the contrapositive:
P ⇒ Q is logically equivalent to ¬Q ⇒ ¬P.
So if ¬Q is more concrete, prove ¬Q ⇒ ¬P directly.
Example: “If n² is even, then n is even.”
Directly from “n² is even” to “n is even” is possible, but a clean approach is contrapositive:
¬(n is even) ⇒ ¬(n² is even)
That is: if n is odd, then n² is odd (easy by substitution n = 2k+1).
Contrapositive proofs are extremely common in CS correctness and number theory.
Contradiction is a technique for when the statement is difficult to construct directly, but the opposite assumption quickly breaks the rules.
The logic idea is:
Formally, it uses that (¬S ⇒ False) implies S.
To prove: S
1) Assume ¬S.
2) Derive a contradiction.
3) Therefore S.
A contradiction can be:
Statements like “There is no integer x such that …” are negations of existential statements.
To prove ¬(∃x, A(x)) by contradiction, you assume the opposite:
Assume ∃x, A(x)
Then pick such an x and derive an impossibility.
That’s often much easier than trying to directly show non-existence.
The claim “√2 is irrational” means:
¬(∃a, b ∈ ℤ with b ≠ 0 such that √2 = a/b in lowest terms)
The contradiction proof assumes there is such a fraction in lowest terms and then shows both a and b must be even, contradicting “lowest terms.”
You don’t need to memorize every detail now, but recognize the pattern:
Both are related but not identical in practice.
| Method | What you assume | What you aim to show | Common feel |
|---|---|---|---|
| Contrapositive | ¬Q | ¬P | Still “forward” reasoning |
| Contradiction | ¬S | False | “Assume opposite, crash” |
If the statement is an implication P ⇒ Q, then a contradiction proof often looks like:
Assume P ∧ ¬Q, derive contradiction.
This is equivalent to proving (P ⇒ Q) because (P ∧ ¬Q) is exactly the negation of (P ⇒ Q).
Most mistakes in contradiction proofs come from negating the target incorrectly.
Example: Negate “∀n ∈ ℕ, S(n)” correctly:
¬(∀n ∈ ℕ, S(n)) ⇔ ∃n ∈ ℕ such that ¬S(n)
So a contradiction proof against a universal statement often begins:
Assume there exists n with ¬S(n).
Let n be such a counterexample.
...
contradiction.
That step (turning ∀ into ∃) is not cosmetic—it changes the whole structure of the proof.
Many CS objects are defined “by size”: lists of length n, trees with n nodes, loops that run n times, sequences defined by recurrence relations.
If a property is true for size 0 (or 1), and if truth for size n forces truth for size n+1, then it’s true for all sizes. That’s the heart of induction.
Induction is not “hand-wavy dominoes”; it’s a rigorous way to prove:
∀n ∈ ℕ, S(n)
To prove ∀n ≥ n₀, S(n):
1) Base case: Prove S(n₀).
2) Inductive step:
3) Conclude ∀n ≥ n₀, S(n).
The “assume S(n)” is not circular because you assume it only for a generic n and use it to prove the next case.
Claim: ∀n ∈ ℕ, 1 + 2 + ⋯ + n = n(n+1)/2.
This is a perfect induction target because:
You’ll see the full worked version in the examples below.
Sometimes S(n+1) depends not just on S(n), but on multiple earlier cases. Then you can use strong induction:
Inductive hypothesis: assume S(k) is true for all k with n₀ ≤ k ≤ n.
Prove S(n+1).
At difficulty 2, the key is: strong induction is still induction—it just gives you a stronger hypothesis.
1) State the domain: n ∈ ℕ, n ≥ 1, etc.
2) Write the inductive hypothesis explicitly (don’t keep it implicit).
3) In the inductive step, start from what you want:
Want: S(n+1)
Use: S(n)
4) Don’t confuse n (arbitrary) with a specific number.
Induction underlies:
It’s one of the most “CS-native” proof techniques because it aligns with how programs are structured.
In CS, many advanced topics are about proving some transformation preserves truth:
Each of those ultimately becomes a statement like:
1) Modular Arithmetic
You often prove things like:
If a ≡ b (mod m), then a + c ≡ b + c (mod m).
That is a direct proof using the definition:
a ≡ b (mod m) ⇔ m ∣ (a − b).
2) Greedy Algorithms
A common proof pattern is an “exchange argument,” often structured as contradiction:
Assume an optimal solution exists that disagrees with the greedy choice.
Modify (“exchange”) it to agree without hurting optimality.
Contradiction to the assumption that greedy was not part of some optimal solution.
3) NP-Completeness
Reductions are implication statements:
x ∈ A ⇒ f(x) ∈ B
x ∉ A ⇒ f(x) ∉ B
You prove these with direct proofs (sometimes via contrapositive).
4) Propositional Logic
Proof techniques train you to manipulate:
This helps when you later formalize satisfiability arguments.
| If your statement looks like… | Try… | Because… |
|---|---|---|
| P ⇒ Q | Direct proof | Most straightforward |
| “For all n…” | Induction | Natural number structure |
| “No such thing exists” | Contradiction | Negation introduces ∃ |
| “If not Q then not P” is easy | Contrapositive | Equivalent to implication |
Good proofs:
That habit will transfer directly to algorithm correctness, complexity arguments, and rigorous ML derivations later (e.g., showing an objective decreases each step).
Prove: If a and b are even integers, then a + b is even.
Assume a and b are even.
By definition of even, ∃k ∈ ℤ such that a = 2k, and ∃m ∈ ℤ such that b = 2m.
Compute the sum:
a + b = 2k + 2m
Factor out 2:
a + b = 2(k + m)
Since k + m ∈ ℤ, we have written a + b as 2·(integer).
Therefore, by the definition of even, a + b is even.
Insight: Direct proofs often follow a “definition → algebra → definition” loop. You unpack the assumption into an existence form, simplify, then repack it into the target definition.
Prove: There is no smallest positive rational number.
Let S be the set of positive rational numbers.
We want to prove: there does not exist r ∈ S such that r ≤ q for all q ∈ S.
Assume for contradiction that there is a smallest positive rational number r.
So r > 0 and for all q > 0 (q rational), we have r ≤ q.
Consider the rational number r/2.
Since r is rational, r/2 is rational. Since r > 0, we also have r/2 > 0.
Therefore r/2 ∈ S.
By “r is the smallest element,” we must have r ≤ r/2.
But r ≤ r/2 implies (multiplying both sides by 2 > 0):
2r ≤ r
So r ≤ 0, which contradicts r > 0.
Therefore our assumption was false, and there is no smallest positive rational number.
Insight: A good contradiction proof constructs a specific object that violates the assumed extremal property (here: if r is “smallest,” r/2 is smaller). This pattern repeats in many CS proofs (minimal counterexample arguments).
Prove: ∀n ∈ ℕ, 1 + 3 + 5 + ⋯ + (2n − 1) = n².
Define S(n): 1 + 3 + 5 + ⋯ + (2n − 1) = n².
We will prove ∀n ∈ ℕ, S(n) by induction.
Base case (n = 1):
Left side = 1.
Right side = 1² = 1.
So S(1) holds.
Inductive hypothesis: Assume S(n) holds for an arbitrary n ≥ 1.
That is, assume:
1 + 3 + 5 + ⋯ + (2n − 1) = n².
Inductive step: Prove S(n+1).
Start with the left side for n+1:
1 + 3 + ⋯ + (2n − 1) + (2(n+1) − 1)
Use the inductive hypothesis to replace the partial sum:
= n² + (2(n+1) − 1)
Simplify the new term:
2(n+1) − 1 = 2n + 2 − 1 = 2n + 1
So the expression becomes:
= n² + (2n + 1)
= n² + 2n + 1
= (n + 1)²
Thus S(n+1) holds.
By induction, ∀n ∈ ℕ, 1 + 3 + ⋯ + (2n − 1) = n².
Insight: Induction works because the (n+1) case contains the n case plus one extra piece. The inductive hypothesis is like a reusable “macro” you’re allowed to substitute once per step.
Most discrete math proofs reduce to a small set of reusable patterns: direct, contradiction, induction.
Direct proof matches implications P ⇒ Q: assume P and derive Q using definitions and known facts.
Contradiction proves S by assuming ¬S and deriving an impossibility; it’s especially effective for non-existence claims.
Be careful negating quantified statements: ¬(∀x, S(x)) ⇔ ∃x such that ¬S(x).
Induction proves ∀n ∈ ℕ statements via a base case and an inductive step (assume S(n) to prove S(n+1)).
Writing the inductive hypothesis explicitly prevents circular reasoning and keeps the proof checkable.
Choosing the right technique is often about recognizing the statement’s logical shape (implication, universal, non-existence).
Negating a statement incorrectly, especially with quantifiers (mixing up ∀ and ∃).
In induction, forgetting to specify the starting index (n ≥ 0 vs n ≥ 1) or proving the wrong base case.
Using the inductive hypothesis for n+1 (what you’re trying to prove) instead of only for n (what you’re allowed to assume).
In direct proofs, skipping the defining step (e.g., claiming “n even” implies “n = 2k” without stating existence of k ∈ ℤ).
Direct proof: Prove that if a is an odd integer and b is an odd integer, then a + b is even.
Hint: Use the definition: odd means a = 2k + 1 for some k ∈ ℤ. Add and simplify into 2·(integer).
Assume a and b are odd.
Then ∃k, m ∈ ℤ such that a = 2k + 1 and b = 2m + 1.
Add:
a + b = (2k + 1) + (2m + 1)
= 2k + 2m + 2
= 2(k + m + 1).
Since k + m + 1 ∈ ℤ, a + b is even by definition.
Contradiction: Prove that there is no integer n such that n is both even and odd.
Hint: Assume n is even and odd. Then n = 2k and n = 2m + 1 for integers k, m. Compare parity.
Assume for contradiction there exists an integer n that is both even and odd.
Then ∃k ∈ ℤ with n = 2k, and ∃m ∈ ℤ with n = 2m + 1.
Set them equal: 2k = 2m + 1.
Then 2k − 2m = 1 ⇒ 2(k − m) = 1.
But the left side is even (a multiple of 2), while the right side is odd. This is impossible.
Therefore no integer is both even and odd.
Induction: Prove that ∀n ∈ ℕ, 1 + 2 + ⋯ + n = n(n + 1)/2.
Hint: Base case n = 1. For the step, write the (n+1) sum as (1+…+n) + (n+1) and substitute the hypothesis.
Let S(n) be the statement 1 + 2 + ⋯ + n = n(n + 1)/2.
Base case (n = 1): left side = 1, right side = 1·2/2 = 1, so S(1) holds.
Inductive hypothesis: assume S(n) holds for some arbitrary n ≥ 1:
1 + 2 + ⋯ + n = n(n + 1)/2.
Inductive step: consider the sum to n+1:
1 + 2 + ⋯ + n + (n + 1)
= (1 + 2 + ⋯ + n) + (n + 1)
= n(n + 1)/2 + (n + 1)
= n(n + 1)/2 + 2(n + 1)/2
= (n(n + 1) + 2(n + 1))/2
= (n + 1)(n + 2)/2
= (n + 1)((n + 1) + 1)/2.
Thus S(n+1) holds. By induction, ∀n ∈ ℕ, 1 + 2 + ⋯ + n = n(n + 1)/2.
Next nodes that heavily rely on these patterns: