On this page
Loading guide controls…
Continue lessonNew guided lessons are not available yet.
Guided lesson options
You stopped at:
ContinueRevision Mode is on. Questions and activities are hidden.
The linked question or activity is hidden by Revision Mode.
When a direct proof is hard to find, three other structures often succeed. A contrapositive proves “if not Q then not P” instead of “if P then Q”; a proof by contradiction assumes the statement is false and derives something impossible; a proof by cases splits the possibilities into a complete list. This lesson writes each kind of proof from definitions, explains when each is the natural choice, and shows why examples can disprove a general statement but never prove one.
Proofs start from definitions
A proof is a chain of statements, each following from definitions, earlier results or the previous lines. Write it so that a reader can check every step without guessing what you meant. Start by replacing each word in the claim with its definition: here, an integer n is even when n = 2k and odd when n = 2k + 1, for some integer k.
Worked example 1
The sum of two odd integers
Worked example 1
The sum of two odd integers
Prove that the sum of any two odd integers is even.
Show full solutionHide solution
Name two arbitrary odd integers
Method
Let m and n be odd, so m = 2a + 1 and n = 2b + 1 for some integers a and b.Reason
Two different letters keep the integers general. Writing m = n = 2k + 1 would prove the claim only for equal integers.Working
Answer
m + n = 2a + 2b + 2 = 2(a + b + 1).
Match the definition of even
Method
a + b + 1 is an integer.Reason
“Even” means “twice an integer”, so the bracket must be shown to be an integer.Working
Answer
So m + n is twice an integer, and therefore even. blacksquare
Quick check
Checking 3 + 5 = 8 and 7 + 9 = 16 illustrates the claim but proves nothing about the infinitely many other pairs. The letters a and b stand for every possible pair at once.
Proving the contrapositive
Sometimes the hypothesis gives you little to work with. “If n² is even, then n is even” starts from n² = 2k, and nothing obvious follows about n. Its contrapositive, “if n is odd, then n² is odd”, starts from n = 2k + 1, which can be squared. Because a conditional and its contrapositive are equivalent, proving either proves both.
Worked example 2
If a square is even, so is the number
Worked example 2
If a square is even, so is the number
Prove that, for every integer n, if n² is even then n is even.
Show full solutionHide solution
State what you will prove
Method
Prove the contrapositive: if n is odd, then n² is odd.Reason
Saying which statement you are proving tells the reader why the conclusion follows.Working
Answer
Let n be odd, so n = 2k + 1 for some integer k.
Square and match the definition
Method
Expand and factor out 2 from all but the final 1.Reason
Odd means “twice an integer, plus one”.Working
Answer
n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. So the contrapositive holds, and therefore so does the original statement. blacksquare
Quick check
Proving the converse, “if n is even then n² is even”, would not prove this statement. Converse and original are different claims.
Proof by contradiction
To prove a statement S by contradiction, assume that S is false and deduce something impossible: a statement together with its negation, or a fact known to be false. Since every deduction was valid, the assumption must be wrong, so S is true.
Worked example 3
√2 is irrational
Worked example 3
√2 is irrational
Prove that square root of 2 is irrational.
Show full solutionHide solution
Assume the opposite, as precisely as possible
Method
Suppose square root of 2 = p/q with integers p, q, q ≠ 0, and the fraction in lowest terms.Reason
Every rational number can be written in lowest terms, so this costs nothing and gives a fact to contradict.Working
Answer
Squaring, p² = 2q², so p² is even. By the previous result, p is even: p = 2r for some integer r.
Reach the contradiction
Method
Substitute p = 2r.Reason
The same argument now applies to q.Working
Answer
4r² = 2q², so q² = 2r² is even and q is even. Then p and q are both even, so p/q is not in lowest terms. This contradicts the assumption, so square root of 2 is irrational. blacksquare
Quick check
Name the contradiction explicitly (“both even, contradicting lowest terms”). Ending with “this is impossible” leaves the reader to guess which assumption failed.
Exam-style question 1
An irrational logarithm
Exam-style question 1
An irrational logarithm
Prove that log ₂ 3 is irrational. [4]
Write your answer, then compare it with the solution
Show full solutionHide solution
Set up the assumption
Method
Suppose log ₂3 = p/q for integers p, q with q > 0.Reason
Since 3 > 1, log ₂3 > 0, so p is positive too.Working
Answer
Then 2^(p/q) = 3, and raising both sides to the power q gives 2^p = 3^q.
Contradict by parity
Method
Compare the parity of the two sides.Reason
A positive power of 2 is even, while every power of 3 is odd.Working
Answer
2^p is even because p ≥ 1, and 3^q is odd. An integer cannot be both even and odd, so the assumption is false and log ₂3 is irrational. blacksquare
Self-mark with the mark scheme
Tick each mark point that your answer includes.
Read your proof line by line. Tick a point only if the step is written down and justified, not merely implied. This self-check does not record a mark.
Common mistake
The positivity step is often missed. If p could be 0, then 2^p = 1 would be odd and there would be no contradiction. Also avoid “assuming p and q have no common factor” and then never using it: an unused assumption suggests the argument has not been understood.
Proof by cases
When a claim covers objects of different kinds, split them into cases that together cover every possibility, and prove the claim in each case. Every integer is even or odd, and every integer has remainder 0, 1, 2 or 3 on division by 4.
Exam-style question 2
Squares and remainders
Exam-style question 2
Squares and remainders
(a) Prove that, for every integer n, n² leaves remainder 0 or 1 on division by 4. [3]
(b) Hence prove that no integer of the form 4k + 3 is a sum of two squares of integers. [2]
Write your answer, then compare it with the solution
Show full solutionHide solution
Case 1: n is even
Method
n = 2k for some integer k.Reason
Even and odd together cover every integer.Working
Answer
n² = 4k², which leaves remainder 0.
Case 2: n is odd
Method
n = 2k + 1.Reason
Write the square as a multiple of 4 plus a remainder between 0 and 3.Working
Answer
n² = 4k² + 4k + 1 = 4(k² + k) + 1, which leaves remainder 1. The two cases cover all integers, proving (a).
Apply the result
Method
Add the possible remainders of two squares.Reason
Remainders on division by 4 add, as long as you reduce the total.Working
Answer
By (a), a² + b² leaves remainder 0 + 0, 0 + 1 or 1 + 1, that is 0, 1 or 2, never 3. So a² + b² ≠ 4k + 3 for any integers a, b, k. blacksquare
Self-mark with the mark scheme
Tick each mark point that your answer includes.
Tick a point only when your written proof contains it. This self-check does not record a mark.
Common mistake
Checking n = 0,1,2,3,4 is not a proof of (a): the cases must cover infinitely many integers, which the algebraic forms 2k and 2k + 1 do. In (b), saying “3 is not a sum of two squares” only checks one number of the form 4k + 3.
Examples cannot prove, but one counterexample disproves
A universal claim, “for all x, P(x)”, is false as soon as one x makes P(x) false. A valid counterexample must satisfy every hypothesis of the claim and fail its conclusion, and you must check both. On the other hand, no number of confirming examples proves a universal claim.
The expression n² + n + 41 is prime for n = 0,1,2,…,39. Forty confirming cases still prove nothing: at n = 40,
which is not prime.
Check your understanding 1
Disprove or prove
Check your understanding 1
Disprove or prove
Decide whether each claim is true. Disprove each false claim with a fully checked counterexample, and give a short proof of each true claim.
- For all real x and y, |x + y| = |x| + |y|.
- For every positive integer n, 2ⁿ + 1 is prime.
- For every integer n, n² + n is even.
Show answerHide answer
- False: x = 1, y = -1 gives |x + y| = 0 but |x| + |y| = 2.
- False: n = 3 gives 2³ + 1 = 9 = 3 × 3. The cases n = 1,2,4 give the primes 3, 5 and 17, which do not help either way.
- True: n² + n = n(n + 1), and one of two consecutive integers is even, so the product is even. Equivalently, prove it by the two cases n even and n odd.
Self-mark with the mark scheme
Tick each mark point that your answer includes.
One mark for each claim. A counterexample earns its mark only when you have checked both the hypothesis and the failed conclusion; a proof earns its mark only when it covers every integer. This self-check does not record a mark.
Existence and uniqueness proofs, the pigeonhole principle and combinatorial proofs follow in later lessons of this topic.
Common mistakes
- Proving the converse instead of the contrapositive.
- In a proof by contradiction, assuming the wrong negation, such as “square root of 2 is rational and in lowest terms” without saying why lowest terms can be chosen.
- Using cases that do not cover every possibility, such as forgetting negative integers or zero.
- Starting a proof from an example instead of a general element defined by the definition.
- Ending without stating what has been proved.
Loading reading progress…
Lesson done
- Monday
- Tuesday
- Wednesday
- Thursday
- Friday
- Saturday
- Sunday
Checking learning on this device…
Change goal
Progress options
Loading questions…