P2 1.1–P2 1.3 - Proof and counterexamples

Mathematical proof

A proof is a sequence of justified logical steps from stated assumptions to a conclusion. An assumption is information you may use; the conclusion is what you must establish. An even integer has the form $2k$, and an odd integer has the form $2k+1$, where $k$ is an integer.

Worked example 1: sum of two odd integers

Question. Prove that the sum of any two odd integers is even.

Plan. Represent the integers independently and show that their sum is twice an integer.

Let the integers be $2k+1$ and $2l+1$, where $k,l$ are integers. Then

Since $k+l+1$ is an integer, this is even.

Answer. The sum of any two odd integers is even.

Check. The independent choice $k=-2,l=3$ gives $-3+7=4$, consistent with the proof. The algebra, rather than this check, covers all choices.

Worked example 2: product of two odd integers

Question. Prove that the product of any two odd integers is odd.

Plan. Expand the product and arrange it as twice an integer plus one.

For integers $k,l$,

The expression $2kl+k+l$ is an integer.

Answer. The product is odd for every pair of odd integers.

Check. With $-3$ and $7$, the product is $-21=2(-11)+1$, which is odd.

Watch out

Do not begin by assuming the result you are trying to prove. “The sum is $2m$, so it is even” has not shown why the given odd integers have that sum. Start from their forms and derive $2m$.

Proof by exhaustion

A proof by exhaustion identifies a complete list of cases, establishes the claim in each case, and concludes that the claim holds for all allowed values. Cases may be individual values or classes represented algebraically.

Worked example 3: a finite list

Question. Prove by exhaustion that $n^2-1$ is a multiple of $3$ for every $n\in\{1,2,4,5\}$.

Plan. Evaluate the expression for all four allowed values.

Every quotient is an integer, including $0$.

Answer. All four allowed values have been checked, so the statement is true on the given set.

Check. The list contains exactly the four members of the stated set. In particular, $0=3\times0$ is a multiple of $3$.

Worked example 4: an infinite set, two cases

Question. Prove by exhaustion that $n^2-1$ is divisible by $3$ for every positive integer $n$ that is not a multiple of $3$.

Plan. Use $n=3k+1$ and $n=3k+2$, where $k$ is a nonnegative integer.

Case 1:

Case 2:

In each case the bracket is an integer, so the expression is divisible by $3$.

Answer. These two cases cover every positive integer not divisible by $3$; hence the statement is true for all such integers.

Check. Division by $3$ permits only remainders $0,1,2$; the assumption excludes $0$. Both remaining cases appear, including $n=1,2$ when $k=0$.

Exam tip

Use a final sentence connecting the cases to the whole allowed set. The forms $3k-1$ and $3k+2$ describe the same remainder class, so using both would miss the remainder-$1$ case.

Counterexample

A counterexample satisfies every assumption of a claim but makes its conclusion false. It disproves a universal statement; an example that satisfies the conclusion cannot establish that universal statement.

Worked example 5: a composite value

Question. Disprove the claim “$n^2+n+11$ is prime for every positive integer $n$”.

Plan. Try $n=10$, so that $n+1=11$ and $n(n+1)$ contains a factor of $11$.

Since $121$ has factors other than $1$ and itself, it is not prime.

Answer. The allowed value $n=10$ is a counterexample, so the claim is false.

Check. $10$ is a positive integer; both factors $11$ are strictly between $1$ and $121$. Both the assumption and the failure have been established.

Worked example 6: the same search strategy

Question. Disprove the claim “$n^2+n+17$ is prime for every positive integer $n$”.

Plan. Choose $n=16$, making $n+1=17$.

Answer. $n=16$ is permitted and produces the composite number $289$, so the universal claim is false.

Check. Independently, $n(n+1)+17=16\times17+17=17(16+1)=17^2$, agreeing with the expanded calculation.

Watch out

A counterexample does not prove the opposite statement for every value. Finding one composite output disproves “every output is prime”; it does not show “every output is composite”.