Direct Proof and Counterexample

In this lesson you’ll learn what a mathematical proof actually is, how to write a direct proof of an if-then statement, the standard definitions for even, odd, and divisible that make these proofs possible, and how to disprove a universal claim with one counterexample.

A proof is a convincing argument that a statement is true for every case it claims to cover, built from definitions, previously established results, and valid logic.

The word “every” is what makes this hard, and it’s also why examples aren’t proofs. Checking a claim for $n = 1, 2, 3, \ldots, 100$ shows it works 100 times. It says nothing about $n = 101$.

A proof can use:

• Definitions. These are the workhorses. Most beginner proofs are just “unfold the definitions and do algebra.”
• Axioms. Basic assumed truths, like the fact that the sum of two integers is an integer.
• Previously proven theorems.
• Valid logical steps.

A proof cannot use: examples, pictures alone, “it’s obvious,” or “everyone knows.”

Almost every proof in this lesson runs on these. Learn them as equations, not as English.

An integer $n$ is even if there exists an integer $k$ with

$$n = 2k$$

An integer $n$ is odd if there exists an integer $k$ with

$$n = 2k + 1$$

An integer $a$ divides $b$, written $a \mid b$, if there exists an integer $k$ with

$$b = ak$$

Read $a \mid b$ as ”$a$ divides $b$,” meaning $b$ is a multiple of $a$ with no remainder. The slashed version $a \nmid b$ means ”$a$ does not divide $b$,” the same way $\neq$ negates $=$. So $3 \mid 12$ is true, and $3 \nmid 7$ is true because 7 leaves a remainder. Careful not to confuse $a \mid b$ (a statement, either true or false) with the fraction $a/b$ (a number).

An integer $n > 1$ is prime if its only positive divisors are 1 and $n$.

Two integers are consecutive if they differ by 1, so they look like $n$ and $n+1$.

The move that makes proofs work: when you’re told something is even, immediately write $n = 2k$. Now you have algebra to do instead of a vague property to reason about.

Most theorems have the form $p \rightarrow q$. A direct proof does this:

1. Assume $p$ is true.
2. Translate $p$ into equations using definitions.
3. Work forward with algebra and logic.
4. Arrive at $q$, translated back into words.

The structure on the page:

Claim. If $p$, then $q$.

Proof. Assume $p$. [definitions, algebra, reasoning] Therefore $q$. ∎

The ∎ (or QED) marks the end. You’ll also see an open box, □.

“If $n$ is even, then $n^2$ is even” really means

$$\forall n \in \mathbb{Z} \, (n \text{ is even} \rightarrow n^2 \text{ is even})$$

That’s why you must work with a general $n$ and never with a specific one. Starting a proof with “let $n = 6$” is fatal, no matter how the algebra goes afterward.

To disprove a universal claim, produce one case where it fails. That’s the negation rule from the quantifiers lesson:

$$\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$$

One counterexample is a complete disproof. You don’t need to explain why the claim is wrong in general, or find a second counterexample, or feel bad about how easy it was.

Be careful about what you’re negating. To disprove “if $p$ then $q$” you need a case where $p$ holds and $q$ fails. A case where $p$ fails tells you nothing, because the implication is vacuously true there.

• Assuming the conclusion - starting from what you want to prove and working backward to something true proves nothing on its own. Write it in the valid direction.
• Using specific numbers - “let’s try $n = 4$: $4^2 = 16$, which is even, so it’s proved.” No. That’s one case.
• Reusing a variable name - if $m$ and $n$ are both even, write $m = 2j$ and $n = 2k$. Using $2k$ for both silently assumes they’re equal, which quietly proves a much weaker claim.
• Circular reasoning - using the theorem, or something equivalent to it, as a step in its own proof.

Example 1: The sum of two even integers is even.

Proof. Let $m$ and $n$ be even integers. By definition there exist integers $j$ and $k$ with $m = 2j$ and $n = 2k$.

Then

$$m + n = 2j + 2k = 2(j + k)$$

Since $j$ and $k$ are integers, $j + k$ is an integer. So $m + n$ equals 2 times an integer, which is the definition of even.

Therefore the sum of two even integers is even. ∎

Notice the shape. Unfold definitions, factor out the 2, point at the definition again. That last step, explicitly noting that $j+k$ is an integer, is what makes it rigorous rather than hand-wavy.

Example 2: If $n$ is odd, then $n^2$ is odd.

Proof. Let $n$ be an odd integer, so $n = 2k + 1$ for some integer $k$.

$$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$$

Let $m = 2k^2 + 2k$, which is an integer since $k$ is. Then $n^2 = 2m + 1$, which is odd by definition.

Therefore if $n$ is odd, $n^2$ is odd. ∎

The trick every time: manipulate the expression into the exact form the definition demands, here $2(\text{something}) + 1$.

Example 3: The product of two consecutive integers is even.

Proof. Let the integers be $n$ and $n+1$. Consider two cases.

Case 1: $n$ is even. Then $n = 2k$, so

$$n(n+1) = 2k(n+1) = 2\big(k(n+1)\big)$$

which is even.

Case 2: $n$ is odd. Then $n + 1 = 2k + 2 = 2(k+1)$ is even, so

$$n(n+1) = n \cdot 2(k+1) = 2\big(n(k+1)\big)$$

which is even.

Every integer is even or odd, so the cases are exhaustive. Therefore $n(n+1)$ is always even. ∎

This is proof by cases. It’s completely legitimate as long as your cases cover every possibility.

Example 4: Divisibility is transitive.

Claim. If $a \mid b$ and $b \mid c$, then $a \mid c$.

Proof. Assume $a \mid b$ and $b \mid c$. By definition there are integers $j$ and $k$ with

$$b = aj \qquad c = bk$$

Substitute the first into the second:

$$c = (aj)k = a(jk)$$

Since $jk$ is an integer, $a \mid c$ by definition. ∎

Short, clean, and it works for every integer at once. Notice again the two distinct variable names.

Example 5: Disprove a claim.

Claim. For every positive integer $n$, the value $n^2 + n + 41$ is prime.

Disproof. Try small values: $n=1$ gives 43 (prime), $n=2$ gives 47 (prime), $n=3$ gives 53 (prime). It keeps working for a while, which is exactly what makes this claim famous.

But take $n = 40$:

$$40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41^2$$

Since $1681 = 41 \cdot 41$, it is not prime. The claim is false. ∎

This one holds for $n = 1$ through $39$ and then breaks. Forty consecutive successes and the claim is still false. That’s the whole argument for why proofs exist.

Example 6: Disprove a converse.

Claim. If $n^2$ is divisible by 4, then $n$ is divisible by 4.

Disproof. Take $n = 6$. Then $n^2 = 36$, and $36 = 4 \cdot 9$, so $n^2$ is divisible by 4. But $6$ is not divisible by 4.

The hypothesis holds and the conclusion fails, so the implication is false. ∎

Proof is the difference between “my tests pass” and “this cannot fail.” Aerospace software, cryptographic protocols, and medical device firmware get formally verified precisely because testing can only ever check finitely many cases, and $n = 40$ might be the one you skipped.

Counterexamples are how security research works. Nobody proves an encryption scheme is unbreakable by trying it a lot. They look for a single input that breaks the guarantee, and one is enough to retire the algorithm.

In everyday engineering, this shows up as edge cases. “Every user has a last name” is a universal claim, and one user in Indonesia with a single mononym is a counterexample that breaks your form validation. Learning to hunt for counterexamples makes you noticeably better at spotting bad assumptions in a spec before they become bugs.

The style of thinking transfers beyond math too. When someone makes a sweeping claim, the productive response is usually not a counter-sweep. It’s one well-chosen example.