Key takeaways
- To prove p → q directly, assume p, use definitions and known results to reason forward, and finish at q.
- A universal statement starts with an arbitrary element: 'Let n be any integer', not a particular number.
- Unpack every definition into an equation you can work with, such as n = 2k + 1 for an odd n.
- Use a new letter for each new unknown: the k for one odd number and the j for another are different.
- Do your scratch work backwards if it helps, but write the final proof forwards from the hypothesis.
A direct proof is the most natural kind of argument: start from what you are given and reason forward until you reach what you want. Levin's Discrete Mathematics: An Open Introduction calls it the simplest style of proof from a logical point of view, and sums up its format in one line: assume P, explain, explain, explain, therefore Q.
The difficulty is rarely the logic. It is knowing what to write in the "explain" lines. This guide gives a template that handles most first-course proofs and five worked examples of increasing difficulty.
The template
For a statement of the form "for every x, if P(x) then Q(x)":
- Introduce an arbitrary object. "Let n be an integer." Arbitrary means you assume nothing about n except what the statement allows.
- Assume the hypothesis. "Suppose n is odd."
- Unpack the definition. "Then n = 2k + 1 for some integer k."
- Manipulate using algebra and results you already know.
- Repack into the conclusion's definition. "So n² = 2m + 1 where m is an integer."
- State the conclusion. "Therefore n² is odd."
Steps 3 and 5 do most of the work, which is why definitions matter so much. You cannot prove something is even without knowing that "even" means "equal to 2 times an integer".
| Term | Definition to unpack |
|---|---|
| n is even | n = 2k for some integer k |
| n is odd | n = 2k + 1 for some integer k |
| a divides b (a ∣ b) | b = ak for some integer k |
| A ⊆ B | every element of A is an element of B |
| x is rational | x = p/q for integers p, q with q ≠ 0 |
Example 1: the sum of two odd integers is even
Proof. Let m and n be odd integers. Then m = 2a + 1 and n = 2b + 1 for some integers a and b. So m + n = 2a + 2b + 2 = 2(a + b + 1). Since a + b + 1 is an integer, m + n is even. ∎
Note the two different letters, a and b. Writing m = 2k + 1 and n = 2k + 1 would silently assume m = n, and the proof would cover only that special case.
Example 2: divisibility of a sum
Claim. For integers a, b and c, if a ∣ b and a ∣ c, then a ∣ (b + c).
Proof. Suppose a ∣ b and a ∣ c. Then b = aj and c = ak for some integers j and k. So b + c = aj + ak = a(j + k). Since j + k is an integer, a ∣ (b + c). ∎
This one fact explains why many divisibility rules work: split a number into parts each divisible by the divisor, and the whole is divisible too.
Example 3: using an earlier result
Claim. If n is odd, then n² − 1 is divisible by 8.
Scratch work. Try n = 3, 5, 7: 8, 24, 48. All multiples of 8. Promising.
Proof. Let n be odd, so n = 2k + 1 for some integer k. Then n² − 1 = 4k² + 4k = 4k(k + 1). The integers k and k + 1 are consecutive, so one of them is even, and therefore k(k + 1) = 2m for some integer m. Hence n² − 1 = 4 · 2m = 8m, which is divisible by 8. ∎
The step "one of two consecutive integers is even" is a separate small fact; in a written proof you either cite it or prove it in a line, by cases on whether k is even or odd.
Example 4: a set inclusion
Claim. If A ⊆ B and B ⊆ C, then A ⊆ C.
Proof. Suppose A ⊆ B and B ⊆ C. Let x be any element of A. Since A ⊆ B, x ∈ B. Since B ⊆ C, x ∈ C. So every element of A is in C, which means A ⊆ C. ∎
This "element-chasing" pattern is how almost every set identity is proved: take an arbitrary element of one side and show it belongs to the other. The set operations guide uses it for unions and intersections.
Example 5: an inequality
Claim. For every real number x > 0, x + 1/x ≥ 2.
Scratch work, backwards. x + 1/x ≥ 2 ⇔ x² + 1 ≥ 2x (multiplying by x > 0) ⇔ x² − 2x + 1 ≥ 0 ⇔ (x − 1)² ≥ 0, which is always true.
Proof, forwards. Let x > 0. Since a square is never negative, (x − 1)² ≥ 0, so x² − 2x + 1 ≥ 0 and x² + 1 ≥ 2x. Dividing by the positive number x gives x + 1/x ≥ 2. ∎
The scratch work starts from the conclusion, which is fine for finding the idea but is not a proof: it assumes what it wants to show. The written proof starts from something known to be true and moves forward. Every step must be reversible or forward-pointing, and here dividing by x is legitimate because x > 0.
Mistakes that cost marks
- Proving by example. Checking n = 3, 5 and 7 is evidence, not proof. Levin's book gives the classic warning: n² − n + 41 produces only primes for the first values of n you try (in fact for every n from 1 to 40), yet n = 41 gives 41² = 1681.
- Reusing a letter. Two odd numbers need two different integers in their definitions.
- Assuming the conclusion. Starting from "n² is odd" to prove "n² is odd" is circular.
- Skipping the definition. "n is odd, so n² is odd" restates the claim. Unpack, compute, repack.
- Losing the quantifier. "Let n = 5" proves something about 5 only. Use an arbitrary n; the predicates and quantifiers guide explains why that justifies a "for all" conclusion.
When to choose another method
A direct proof works best when the hypothesis gives you something concrete to compute with. When it does not, two indirect methods help. Proof by contrapositive proves ¬q → ¬p instead, which is often easier when the conclusion is a negative statement or when knowing about n² gives you little about n. Proof by contradiction assumes the whole statement fails and derives an impossibility, the usual route for irrationality and "there is no largest" results. Richard Hammack's free Book of Proof, approved by the American Institute of Mathematics' Open Textbook Initiative, gives each method its own chapter and is a good source of further exercises.
Discrete Math: Study & Quiz has a proof techniques unit, broken into topics and lessons with knowledge checks; it is listed with our other education apps. The discrete math hub has the other proof guides.
Good to know
Frequently asked questions
What is a direct proof?
How do I start a direct proof?
Why can't I prove something by checking examples?
When should I use a different proof method?
Sources
- Proofs: Direct Proof (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
- Book of Proof, 3rd edition (Richard Hammack) (opens in a new tab)Richard Hammack (open textbook) — accessed
- A Review of Methods of Proof (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.