What is the difference between proof and checking examples?

Checking examples only tests some cases. A proof uses algebra to show the result must be true for every case.

How do I write an even or odd number in a proof?

Use 2n for even and 2n+1 for odd, saying that n is an integer. Use different letters if you need two numbers.

How many marks is a counter-example worth?

Usually 2 marks: one for a suitable value with working, and one for the conclusion that the statement is false.

When do I use proof by exhaustion?

When you can split all possibilities into a small number of cases, such as even and odd or the remainders when dividing by 3.

Year 12 proof revision notes to download as PDF

This Year 12 proof revision notes is written for pupils aged 16-17 and follows the National Curriculum. In short, it shows you how to construct proofs by deduction and exhaustion and disprove by counter-example. Before you start, you can look back at Year 11 GCSE maths if you need a quick reminder.

Key points

Proof starts from known facts and uses logical steps to reach a conclusion; testing examples never proves a general statement.
Even numbers are \(2n\) and odd numbers are \(2n+1\); consecutive integers are \(n\), \(n+1\), \(n+2\); multiples of 3 are \(3n\).
Proof by deduction: expand and simplify, then state the result as a multiple of the required number.
Proof by exhaustion splits all possibilities into a finite number of cases, such as even or odd, or remainders 0, 1, 2 when dividing by 3, and checks each one.
One counter-example is enough to disprove a statement; always show the numbers and check that the statement fails.
Proof by contradiction assumes the opposite, follows logical steps to something impossible, and concludes the original is true (irrationality of \(\sqrt2\), infinitely many primes).

Year 12 proof revision notes: what you will learn

At A level you must do more than get answers: you must show that a statement is always true, or show that it is false. Proof is marked for logic and clear communication, so every line must follow from the one before. This chapter covers proof by deduction, proof by exhaustion and disproof by counter-example.

Starter activity

Choose any two odd numbers and add them. Do it again with two other odd numbers. What type of number do you always get? Now try four more pairs. Are you certain it will always work? Write down how you could convince a sceptical friend without trying every pair of odd numbers in the world. Write one odd number using the letter \(n\).

Key vocabulary and algebraic representation

Definition: statement, conjecture and proof

A statement is a sentence that is either true or false. A conjecture is a statement you believe is true but have not yet proved. A proof is a chain of logical steps from known facts to the result. Use \(\therefore\) for "therefore" and finish with a conclusion in words.

Watch out

Testing a few cases is not a proof. The statement might fail for the next case.

Key fact: algebraic forms of integers

Let \(n\) be an integer. An even number is \(2n\) and an odd number is \(2n+1\). Consecutive integers are \(n\) and \(n+1\); three consecutive integers are \(n-1\), \(n\), \(n+1\). A multiple of 3 is \(3n\). Always say that \(n\) is an integer, and use a different letter for each different number (\(2a+1\) and \(2b+1\), never \(2n+1\) twice).

Proof by deduction

Definition: proof by deduction

Start from general algebra and use valid rules of algebra, step by step, to reach the result.

Worked example 1

Prove that the sum of any three consecutive integers is a multiple of 3.

Let the integers be \(n-1\), \(n\) and \(n+1\), where \(n\) is an integer. Their sum is \((n-1)+n+(n+1)=3n\). Since \(n\) is an integer, \(3n\) is a multiple of 3. \(\blacksquare\)

Worked example 2

Prove that the product of two odd numbers is odd.

Let the numbers be \(2a+1\) and \(2b+1\) with \(a,b\) integers. Then \((2a+1)(2b+1)=4ab+2a+2b+1=2(2ab+a+b)+1\). Because \(2ab+a+b\) is an integer, this has the form \(2k+1\), so it is odd. \(\blacksquare\)

Note: a picture proof

The big square has side \(a+b\) and is cut into a square of area \(a^2\), a square of area \(b^2\) and two rectangles of area \(ab\). So \((a+b)^2=a^2+2ab+b^2\).

Worked example 3

Prove that \((2n+1)^2-1\) is a multiple of 4 for every integer \(n\).

\((2n+1)^2-1=4n^2+4n+1-1=4n^2+4n=4n(n+1)\). This is 4 times an integer, so it is a multiple of 4. \(\blacksquare\) In fact \(n(n+1)\) is always even, so the result is always a multiple of 8.

Worked example 4

Prove that \(x^2-8x+20>0\) for all real \(x\).

Complete the square: \(x^2-8x+20=(x-4)^2+4\). A square is never negative, so \((x-4)^2\ge0\) and the expression is at least 4. It is therefore always positive. \(\blacksquare\)

Worked example 5

Prove that \(a^2+b^2\ge2ab\) for all real \(a,b\).

Start from the true fact \((a-b)^2\ge0\). Expanding gives \(a^2-2ab+b^2\ge0\), and adding \(2ab\) to both sides gives \(a^2+b^2\ge2ab\). \(\blacksquare\)

Watch out

Work towards the result from a true fact. Never start by assuming the result you want to prove.

Proof by exhaustion

Definition: proof by exhaustion

Split all the possibilities into a finite number of cases and check every case.

Worked example 6

Prove that the square of any integer has the form \(3k\) or \(3k+1\).

Every integer is \(3m\), \(3m+1\) or \(3m+2\). Case 1: \((3m)^2=9m^2=3(3m^2)\). Case 2: \((3m+1)^2=9m^2+6m+1=3(3m^2+2m)+1\). Case 3: \((3m+2)^2=9m^2+12m+4=3(3m^2+4m+1)+1\). All cases are covered, so the result holds. \(\blacksquare\)

Disproof by counter-example

Definition: counter-example

A counter-example is a single case that satisfies the conditions of a statement but makes it false. One is enough to disprove a statement.

Worked example 7

Disprove: "\(n^2+n+41\) is prime for every positive integer \(n\)."

Take \(n=40\): \(1600+40+41=1681=41^2\), which is not prime. So the statement is false. \(\blacksquare\)

Watch out

A counter-example must really satisfy the conditions of the statement. Show the working, then write "so the statement is false".

Writing a proof

Rule: what counts as proof

A proof must be valid for every case in the statement. Use letters (not numbers) for deduction, cover all cases for exhaustion, and use exactly one valid case to disprove.

Method: structure of a written proof

Define your letters and say what type of number they are ("let \(n\) be an integer").
Set up the algebra for the statement.
Simplify, factorise or complete the square, one clear step at a time.
Point out the key feature (a factor of 3, the form \(2k+1\), a square being at least 0).
Write a short conclusion that answers the question in words.

Note: exam wording

In "show that" questions the final line is given, so make every step visible. Marks are awarded for method (M), accuracy (A) and communication, so the written reasons matter as much as the algebra.

Watch out

Common errors: checking examples and saying "so it is always true"; forgetting to say that letters stand for integers; not finishing with a conclusion that links back to the question.

Worked example 8: Proof by deduction: a cube minus the number

Prove that \(n^3-n\) is divisible by 6 for every positive integer \(n\).

Factorise: \(n^3-n=n(n-1)(n+1)\), the product of three consecutive integers \((n-1),n,(n+1)\). Among any three consecutive integers at least one is even, so the product is divisible by 2. Exactly one of them is a multiple of 3, so the product is divisible by 3. Since 2 and 3 share no common factor, the product is divisible by \(2\times3=6\). Check: \(n=4\) gives \(60=6\times10\).

Worked example 9: Proof by exhaustion with remainders

Prove that the square of any integer is either a multiple of 3 or one more than a multiple of 3.

Every integer has the form \(3k\), \(3k+1\) or \(3k+2\). Then \((3k)^2=9k^2=3(3k^2)\), a multiple of 3. \((3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1\), one more than a multiple of 3. \((3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1\), one more than a multiple of 3. The three cases cover every integer, so the statement is proved.

Worked example 10: Disproof using a context

A shop owner says: "If I buy \(n\) identical items and each costs a whole number of pounds, the total with 20% VAT is always a whole number of pounds." Is this true?

The total including VAT is \(1.2\times n\times c\) where \(c\) is the price in pounds. Take \(n=1\) and \(c=1\): the total is £1.20, which is not a whole number of pounds. So the statement is false and a single counter-example (one £1 item) is enough. In general \(1.2nc=\tfrac65nc\) is a whole number only when \(nc\) is a multiple of 5.

Worked example 11: Proof by contradiction: no integer solution

Prove that the equation \(x^2-y^2=2\) has no integer solutions.

Assume \(x\) and \(y\) are integers with \((x-y)(x+y)=2\). The numbers \(x-y\) and \(x+y\) differ by \(2y\), which is even, so they have the same parity (both odd or both even). If both are odd, their product is odd, not 2. If both are even, their product is a multiple of 4, not 2. Either case gives a contradiction, so there are no integer solutions.

Worked example 12: A proof about a sequence

The sequence \(u_n=n^2+n+41\) gives primes for \(n=0,1,2,\dots\) Show that it does not give a prime for every \(n\).

When \(n=41\), \(u_{41}=41^2+41+41=41(41+1+1)=41\times43=1763\), which has factors 41 and 43, so it is not prime. A single counter-example disproves the claim, even though the first 40 values are all prime. Mathematicians say that checking many cases never proves a statement, but a single failure disproves it.

Method: choosing the right type of proof

Read the command word. "Show that", "prove that" and "verify" all demand a logical argument, not a few examples.
If the statement is about all integers, write general expressions using \(n\) (or \(2n\), \(2n+1\), \(3n+1\) for particular types).
Choose: direct algebra for identities, exhaustion when there are finitely many cases, contradiction when the opposite assumption leads to something impossible (irrationality, infinitely many).
Finish with a conclusion in words that answers the question, such as "so the sum is always even".

Watch out: common proof mistakes

Testing a few numbers and saying "so it is always true". Examples never prove a general statement.
Using the same letter for two different integers, such as writing two consecutive even numbers as \(2n\) and \(2n+2\) but two separate even numbers as \(2n\) and \(2n\).
Forgetting the conclusion. Mark schemes award a mark for explaining that the expression is "a multiple of" the required number.
Starting from what you want to prove and "working both sides" without making the logic reversible.

Did you know?

Fermat claimed that \(2^{2^n}+1\) is prime for all \(n\). It works for \(n=0,1,2,3,4\) (giving 3, 5, 17, 257, 65537). But in 1732 the Swiss mathematician Leonhard Euler showed that for \(n=5\) the number \(4\,294\,967\,297\) equals \(641\times6\,700\,417\). A single counter-example demolished a claim that had stood for nearly a century.

Otto’s tip

To prove something is a multiple of \(k\), keep factorising until you can see \(k\times\)(an integer). To prove it is positive, try to write it as a square plus a positive number.

How to use this Year 12 proof revision notes

First, read the key points so that you know where the Year 12 proof revision notes is going. Then work through each definition and worked example, and cover the solution before you read it. After that, practise with the proof worksheet and check every question with the worksheet answers. When you feel ready, test yourself with the multiple choice questions or the quick quiz. Finally, sit the proof test and mark it with the test answers.

Also, the starters are a good warm-up, so you can keep the key facts fresh. Moreover, all the pages of this chapter work together, so you can move between them at any time. For example, many pupils read the lesson on Monday, practise on Wednesday and test themselves on Friday. In short, this Year 12 proof revision notes gives you everything you need for the chapter.