Skip to main content

Direct proof and counterexample

Forty examples in a row can still mislead. Learn the difference between claims about every case and claims that some case exists, why one counterexample is enough to sink a claim about every case, and how a direct proof chains definitions to a conclusion with every link justified.
M01.6.3L0 Foundation25 minIn review

Before this lesson

M01.6.2 Statements and logic: and, or, not, if-then

After this lesson you can

  • Tell a for-all claim from a there-exists claim, and say what proves and what disproves each.
  • Disprove a for-all claim with one counterexample, and explain why no number of examples can prove one.
  • Write a direct proof from the definitions of even and odd, justifying every step.
  • Search for a counterexample with a loop and with the built-ins all and any, and explain why a passing test is evidence, not proof.

In review. The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

The question

The formula \({n^2 + n + 41}\) gives 41, 43, 47, 53, …, and every value is a prime number, for \({n = 0, 1, 2}\) and on, all the way to \({n = 39}\). Forty primes in a row. A model that passes forty tests in a row feels just as safe. Is the formula prime for every \({n}\)? And if forty examples cannot settle it, what can?

From the last lesson

1. When is “if \({P}\), then \({Q}\)” false?

Show answer

Only when \({P}\) is true and \({Q}\) is false. In the other three rows of its truth table it is true.

2. “If \({x}\) is a multiple of 4, then \({x}\) is even” is true. Is its converse true?

Show answer

No. The converse, “if \({x}\) is even, then \({x}\) is a multiple of 4”, fails at \({x = 2}\).

Intuition

The question is about primes: whole numbers bigger than 1 whose only whole-number factors are 1 and the number itself. So 2, 3, 5, 7 and 41 are prime, while 1 is not, and nor is \({9 = 3 \times 3}\).

There are two ways to be sure of a claim about numbers, and only one of them can fail you.

The first is to try examples. That can only ever cover the cases you tried. The second is a proof: a chain of statements in which the first is what you are given, the last is what you want, and every link is justified by a definition, a rule of algebra or a fact already proved. Because the chain uses letters instead of particular numbers, it covers every case at once.

A vertical flowchart of six boxes joined by green arrows. The top box, outlined in blue and marked given, reads a and b are even. Then: a equals 2k and b equals 2m, with k and m integers; a plus b equals 2k plus 2m; a plus b equals 2 times k plus m; a plus b equals 2 times an integer. The bottom box, outlined in vermillion and marked to be proved, reads a plus b is even. Each arrow carries its reason in green: definition of even, a new letter for each; add the two equations; take out the common factor 2; k plus m is an integer; definition of even.
M01.6.3-F1

A direct proof as a flowchart. Each green arrow is one justified step, so the bottom box is as certain as the top one.

Read the chart from the top. The given fact is turned into an equation by a definition, the equations are added, a factor is taken out, and a definition turns the result back into words. Nothing in the chain depends on which even numbers \({a}\) and \({b}\) are, so it proves the claim for all of them.

Build it up

Step 1. Two kinds of claim. A for-all claim says that every case has some property: “for every integer \({n \ge 0}\), \({n^2 + n + 41}\) is prime”. A there-exists claim says that at least one case has it: “some even number is prime”. In symbols, \({\forall}\) reads “for all” and \({\exists}\) reads “there exists”.

Step 2. What settles each kind. The two kinds are proved and disproved in opposite ways:

claim to prove it to disprove it
for all an argument for every case one counterexample
there exists one example an argument for every case

“Some even number is prime” is proved by one example, 2. “Every \({n}\) gives a prime” needs an argument, because no list of examples can reach every \({n}\). But it is sunk by a single case where it fails, called a counterexample.

The reason is how “not” acts on these claims. “It is not true that every case has the property” means the same as “some case does not have it”. So disproving a for-all claim is proving a there-exists claim, and one example does that.

Step 3. The counterexample at 40. Keep going past 39. At \({n = 40}\), the first two terms share a factor of 40, and the result is a perfect square:

\[ \begin{aligned} &40^2 + 40 + 41 \\ &\quad = 40 \times 40 + 40 + 41 \\ &\quad = 40 \times 41 + 41 \\ &\quad = 41 \times 41 = 1681. \end{aligned} \]

The third line adds one more 40 to 40 lots of 40, which makes 41 lots of 40, that is \({40 \times 41}\). The last line adds one more 41 to 40 lots of 41, which makes 41 lots of 41. A number with the factor 41, other than 41 itself, is not prime. So the claim is false, even though it held forty times in a row.

A grid of fifty tiles numbered 0 to 49, ten to a row. The first four rows, n from 0 to 39, are all pale green, and a green bracket beside them reads n equals 0 to 39, all prime. In the last row the tiles 40, 41, 44 and 49 are reddish purple with thick borders and bold numbers, and a bracket reads four fail. Text below: n equals 40 gives 40 squared plus 40 plus 41 equals 1681 equals 41 times 41, the first that is not prime; and 41 gives 1763 equals 41 times 43, 44 gives 2021 equals 43 times 47, 49 gives 2491 equals 47 times 53.
M01.6.3-F2

Forty successes do not prove a for-all claim; one failure disproves it. The first failure is at \({n = 40}\).

Step 4. Definitions are the raw material. A proof can only use what is known, and the most useful facts are definitions. An integer \({n}\) is even if \({n = 2k}\) for some integer \({k}\), and odd if \({n = 2k + 1}\) for some integer \({k}\). So 10 is even because \({10 = 2 \times 5}\), and 7 is odd because \({7 = 2 \times 3 + 1}\). We accept the known fact that every integer is even or odd, and never both.

Step 5. The shape of a direct proof. Most claims have the form “if \({P}\), then \({Q}\)” for every case. A direct proof starts by supposing \({P}\) about a case named only by letters, and uses definitions and algebra to reach \({Q}\). Since an if-then can only be false when \({P}\) is true and \({Q}\) false, showing that \({P}\) forces \({Q}\) rules out the one bad row.

The formal statement

NoteDefinitions: even, odd, counterexample

An integer \({n}\) is even if \({n = 2k}\) for some integer \({k}\), and odd if \({n = 2k + 1}\) for some integer \({k}\). A counterexample to a claim “for every \({x}\), \({P(x)}\)” is one \({x}\) for which \({P(x)}\) is false.

Negating the two kinds of claim. For any open sentence \({P(x)}\),

\[ \begin{aligned} \neg\big(\forall x,\ P(x)\big) &\equiv \exists x,\ \neg P(x), \\ \neg\big(\exists x,\ P(x)\big) &\equiv \forall x,\ \neg P(x). \end{aligned} \]

These are De Morgan’s laws again, for any number of cases: “every case” is a long “and”, “some case” a long “or”, and “not” swaps them.

Proposition 1. If \({a}\) and \({b}\) are even integers, then \({a + b}\) is even.

Proof. Suppose \({a}\) and \({b}\) are even. By the definition of even, \({a = 2k}\) and \({b = 2m}\) for some integers \({k}\) and \({m}\). The two letters differ because \({a}\) and \({b}\) may be different numbers. Adding the two equations,

\[ \begin{aligned} a + b &= 2k + 2m \\ &= 2(k + m). \end{aligned} \]

The second line takes out the common factor 2 (the distributive law of M01.1.2). The sum \({k + m}\) of two integers is an integer, so \({a + b}\) is 2 times an integer. By the definition of even, \({a + b}\) is even. \({\blacksquare}\)

Proposition 2. If \({n}\) is an odd integer, then \({n^2}\) is odd. The worked example proves it.

Go deeper: why this formula was bound to fail by n = 41

At \({n = 41}\) every one of the three terms is a multiple of 41:

\[ \begin{aligned} &41^2 + 41 + 41 \\ &\quad = 41 \times (41 + 1 + 1) \\ &\quad = 41 \times 43. \end{aligned} \]

So the claim had to fail by \({n = 41}\) at the latest; it fails one step earlier because \({40^2 + 40 = 40 \times 41}\). More is true: Lehman, Leighton and Meyer note that no polynomial with integer coefficients, other than a constant, gives a prime for every \({n \ge 0}\).

Worked example

Prove that the square of every odd integer is odd, and follow the proof with \({n = 7}\).

The proof is in letters, so it covers every odd integer at once. The column of numbers beside it is not part of the proof; it only shows one case going through the same steps.

Two columns of five boxes. The left column, headed in letters, reads from top to bottom: n is odd, outlined in blue; n equals 2k plus 1; n squared equals 4k squared plus 4k plus 1; n squared equals 2 times the bracket 2k squared plus 2k, plus 1; n squared is odd, outlined in vermillion. Green arrows between the boxes carry the reasons: definition of odd, square it out, take out a factor 2, definition of odd. The right column, headed with n equals 7, so k equals 3, follows the same steps in sky-blue boxes: 7 is odd; 7 equals 2 times 3 plus 1; 49 equals 36 plus 12 plus 1; 49 equals 2 times 24 plus 1; 49 is odd. A note below says the last step uses that 2k squared plus 2k is an integer, which for k equal to 3 is 24.
M01.6.3-F3

The worked-example trace. The left column is the proof; the right column follows one case, \({n = 7}\), through the same steps.

Step 1. Suppose \({n}\) is odd. By the definition of odd, \({n = 2k + 1}\) for some integer \({k}\). (For \({n = 7}\), \({k = 3}\).)

Step 2. Square both sides. The square of a sum expands by the rule of M01.1.2,

\[ (a + b)^2 = a^2 + 2ab + b^2, \]

here with \({a = 2k}\) and \({b = 1}\):

\[ \begin{aligned} n^2 &= (2k + 1)^2 \\ &= (2k)^2 + 2 \times 2k \times 1 + 1^2 \\ &= 4k^2 + 4k + 1. \end{aligned} \]

For \({n = 7}\) the last line reads 49 on the left and 36, 12 and 1 on the right, which add to 49.

Step 3. Take the factor 2 out of the first two terms:

\[ n^2 = 2(2k^2 + 2k) + 1. \]

For \({n = 7}\) the bracket is \({18 + 6 = 24}\), and \({2 \times 24 + 1 = 49}\).

Step 4. The bracket \({2k^2 + 2k}\) is an integer, because products and sums of integers are integers. So \({n^2}\) is 2 times an integer, plus 1. By the definition of odd, \({n^2}\) is odd. \({\blacksquare}\)

Notice where the letter \({k}\) came from: the definition of odd hands it to us. Direct proofs about even and odd numbers usually start this way, by turning words into an equation.

Code

A computer is a fast tireless example-checker, which makes it a good counterexample hunter and no prover at all. First a test for primes. If \({n}\) has a factor pair \({d \times e}\) with \({d \le e}\), then \({d \times d \le n}\), so it is enough to try divisors \({d}\) while \({d \times d \le n}\).

def is_prime(n):
    # 0 and 1 are not prime
    if n < 2:
        return False
    d = 2
    # a factor, if any, has
    # d * d no bigger than n
    while d * d <= n:
        # % is the remainder;
        # 0 means d divides n
        if n % d == 0:
            return False
        d = d + 1
    return True

# try n = 0, 1, ..., 99
for n in range(100):
    value = n * n + n + 41
    if not is_prime(value):
        print("n =", n, "gives", value)
        # // divides and drops
        # any remainder
        print(value, "=", 41, "x",
              value // 41)
        # one is enough: stop
        break
n = 40 gives 1681
1681 = 41 x 41

The built-in all takes a list of truth values and answers “are they all true?”; any answers “is at least one true?”. They are the for-all and the there-exists of Python.

# n = 0 to 39: all prime?
checks_40 = []
for n in range(40):
    value = n * n + n + 41
    ok = is_prime(value)
    checks_40.append(ok)
print("n = 0 to 39:", all(checks_40))

# n = 0 to 49
checks_50 = []
for n in range(50):
    value = n * n + n + 41
    ok = is_prime(value)
    checks_50.append(ok)
print("n = 0 to 49:", all(checks_50))

# an even prime up to 100?
evens = []
for n in range(2, 101, 2):
    evens.append(is_prime(n))
print("an even prime:", any(evens))
n = 0 to 39: True
n = 0 to 49: False
an even prime: True

Forty Trues prove nothing about \({n = 40}\); one False settles the question. The same holds for any test of code or of a model: a test that passes is one more example. Here are a thousand and two of them for Proposition 2, which only the proof covers in full.

# odd n from -1001 to 1001
squares_odd = []
for n in range(-1001, 1002, 2):
    squares_odd.append(n * n % 2 == 1)
print("cases:", len(squares_odd))
print("all odd:", all(squares_odd))
cases: 1002
all odd: True

Explore

The module’s Venn and truth-table explorer shows the other way to be certain: when the cases are few, check them all. A law about two sets is a for-all claim about elements, but every element falls in one of only four regions. Choose \({(A \cap B)^c}\), press “Other side of the law”, and compare all four rows: that check is a complete proof, called a proof by cases.

Pitfalls

Two panels, each a grid of 25 points for the pairs a and b of even numbers from 0 to 8, with a running across and b running up. The left panel, marked with a cross and titled same letter, a equals 2k, b equals 2k, fills in reddish purple only the five points on the diagonal where a equals b; the other twenty points are hollow, and the note reads covers only the pairs with a equal to b. The right panel, marked with a tick and titled two letters, a equals 2k, b equals 2m, fills all 25 points in green, with the note covers every pair of even numbers.
M01.6.3-F4

Wrong beside right. Writing both even numbers with the same letter quietly assumes they are equal, so the “proof” covers only the diagonal.

“Let \({a = 2k}\) and \({b = 2k}\).”

One letter for two numbers forces \({a = b}\), so the argument covers only pairs of equal numbers. It can even “prove” false claims: with one letter, \({a + b = 4k}\), which suggests that the sum of two even numbers is a multiple of 4. But \({2 + 4 = 6}\) is not. Give each unknown its own letter.

“It worked for every case I tried, so it is true.”

Forty values of \({n^2 + n + 41}\) are prime and the forty-first is not. Examples are evidence; a for-all claim needs an argument that covers every case.

“The opposite of ‘every \({x}\) has the property’ is ‘no \({x}\) has it’.”

The negation is “at least one \({x}\) lacks it”. The opposite of “every model in the list beats the baseline” is “some model does not”, which one bad model shows, not “no model does”.

“All the tests pass, so the code is correct.”

A test checks one input. Passing tests are examples, which is why a failing test is so valuable: it is a counterexample. Code is shown correct for every input by an argument, which is the subject of the next lesson.

Check yourself

Recall

1. What does it take to prove a for-all claim, and what does it take to disprove one?

Show answer

Proving it needs an argument that covers every case. Disproving it needs one counterexample.

2. State the definitions of an even and an odd integer.

Show answer

\({n}\) is even if \({n = 2k}\) for some integer \({k}\), and odd if \({n = 2k + 1}\) for some integer \({k}\).

3. What is \({n^2 + n + 41}\) at \({n = 40}\), and why is it not prime?

Show answer

It is \({1681 = 41 \times 41}\). It has the factor 41, so it is not prime.

4. In a proof about two even numbers \({a}\) and \({b}\), why write \({a = 2k}\) and \({b = 2m}\) rather than \({b = 2k}\)?

Show answer

The same letter would force \({a = b}\), so the proof would only cover pairs of equal numbers.

5. What is the negation of “every email in the batch is spam”?

Show answer

“At least one email in the batch is not spam.”

Exercises

1. ★ Prove that the sum of two odd integers is even.

Show solution

Suppose \({a}\) and \({b}\) are odd. By the definition, \({a = 2k + 1}\) and \({b = 2m + 1}\) for some integers \({k}\) and \({m}\). Then

\[ \begin{aligned} a + b &= 2k + 2m + 2 \\ &= 2(k + m + 1). \end{aligned} \]

\({k + m + 1}\) is an integer, so \({a + b}\) is 2 times an integer: it is even. \({\blacksquare}\)

2. ★★ Prove or disprove each claim. (a) For every natural number \({n}\), \({2^n + 1}\) is prime. (b) For every integer \({n}\), \({n^2 + n}\) is even.

Show solution

(a) False. \({2^1 + 1 = 3}\) and \({2^2 + 1 = 5}\) are prime, but \({2^3 + 1 = 9}\), which is \({3 \times 3}\). The counterexample \({n = 3}\) disproves the claim.

(b) True. Every integer is even or odd, so take the two cases. If \({n = 2k}\), then

\[ \begin{aligned} n^2 + n &= 4k^2 + 2k \\ &= 2(2k^2 + k), \end{aligned} \]

which is even. If \({n = 2k + 1}\), then

\[ \begin{aligned} n^2 + n &= (4k^2 + 4k + 1) \\ &\quad + (2k + 1) \\ &= 4k^2 + 6k + 2 \\ &= 2(2k^2 + 3k + 1), \end{aligned} \]

which is even. In both cases \({n^2 + n}\) is even. \({\blacksquare}\)

3. ★★★ Find the flaw. “Claim: the sum of two even integers is a multiple of 4. Proof: let \({a = 2k}\) and \({b = 2k}\). Then \({a + b = 4k}\), a multiple of 4.” Give a counterexample to the claim, name the line that is wrong, and say what the correct proof does show.

Show solution

Counterexample: \({2 + 4 = 6}\), and 6 is not a multiple of 4. The wrong line is “\({b = 2k}\)”: it uses the letter of \({a}\) again, which assumes \({b = a}\). With a new letter, \({b = 2m}\), the sum is \({2(k + m)}\). That shows the sum is even, and it is a multiple of 4 only when \({k + m}\) is even, which need not happen (\({k = 1}\), \({m = 2}\)).

Summary card

Examples can sink a for-all claim but never prove one; a proof covers every case by working with letters.

The anchor figure again: a vertical flowchart from a and b are even, through a equals 2k and b equals 2m, a plus b equals 2k plus 2m and a plus b equals 2 times k plus m, to a plus b is even, with a green reason on every arrow.
M01.6.3-F1

Every link justified.

  • For all is proved by an argument and disproved by one counterexample.
  • There exists is proved by one example.
  • Even: \({n = 2k}\). Odd: \({n = 2k + 1}\), with \({k}\) an integer.
  • Direct proof: suppose \({P}\), apply definitions and algebra, reach \({Q}\).
  • Python: all(...) is “for all”, any(...) is “there exists”, over the cases you supply.

Sources and next steps

Sources. Each was opened and checked against this lesson on 12 November 2026.

  • Richard Hammack, Book of Proof, third edition (free PDF). Section 2.7: the quantifiers “for all” and “there exists” (Definition 2.1). Section 2.10: negating them, equations (2.8) and (2.9). Section 4.2: even and odd (Definitions 4.1 and 4.2) and prime (Definition 4.5). Section 4.3: the outline of a direct proof, the proof that the square of an odd number is odd, and the advice to use a new letter when one is already taken. Section 9.1: disproof by counterexample, with \({n^2 - n + 11}\) failing at \({n = 11}\).
  • Eric Lehman, F. Thomson Leighton and Albert R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018. Section 1.1, Claim 1.1.3: \({n^2 + n + 41}\) is prime from \({n = 0}\) to 39 (\({p(39) = 1601}\)), and \({p(40) = 41 \times 41}\), with a prime defined as an integer greater than 1 that no other integer greater than 1 divides. The same section notes that no polynomial with integer coefficients, unless it is a constant, is prime for every non-negative integer.
  • Python Software Foundation, Built-in functions: all and any: all is true when every element is true (or the list is empty), and any when at least one is.

Next. M01.6.4 Contradiction and induction adds two more kinds of proof, and uses Proposition 2 to show that \({\sqrt{2}}\) is not a fraction.

This lesson unlocks

M01.6.4 Contradiction and induction

Your progress is saved in this browser only. No account, no tracking.
Back to top