Proof

A LevelAQAEdexcelOCR

Proof Revision

Proof

You may be asked to prove something in mathematics. There are a number of different types of proof questions that you will encounter.

There are 4 skills for proof that you need to understand.

A LevelAQAEdexcelOCR

Skill 1: Proof Notation

The following notation will be used throughout proofs, but will also be relevant to topics later in the course.

 

A set is a collection of objects or numbers (called elements). A set is denoted using a capital letter, and curly brackets are used to show what is in the set, e.g. A = \{3,4,5 \}.

You can write sets in various different ways:

  • as a list of elements: e.g. \{3,4,5\}
  • as a rule: e.g. \{\text{prime numbers}\text{ between 0 and 10}\}
  • as mathematical notation: e.g. \{x : x > 5 \} – this means “the set of values such that x is greater than 5

 

There are different variations of an = sign that you need to be aware of:

  • \neq means “not equal to”
  • \approx means “approximately equal to”
  • \equiv means two things are “equivalent”. It is called the identity symbol.

 

There are logic symbols that you need to understand:

  • p \Rightarrow q” means “if p then q” or “p implies q
  • p \iff q” means “p if and only if q” or “p implies q and q implies p

Note: “if and only if” can be written as “iff”

A LevelAQAEdexcelOCR

Skill 2: Direct Proof

A direct proof (or proof by deduction) is a proof where a statement is proven to be true using fundamental mathematical principles.

Example: Prove that n^2 - 6n + 11 is positive for any integer.

Completing the square gives

\textcolor{red}{(n-3)^2} + \textcolor{blue}{2}

\textcolor{red}{(n-3)^2} is always positive, since it is a square number.

Therefore, if we add \textcolor{blue}{2} to the square number, then the result is still positive.

Hence, n^2 - 6n + 11 is positive for any integer.

A LevelAQAEdexcelOCR

Skill 3: Proof by Exhaustion

In a proof by exhaustion, you will need to break situations down into two or more cases and try all possibilities to prove that the statement holds true for each case.

Example: Prove the following statement:

“For any integer x, f(x)=3x^2+3x-2 is an even integer”

 

We need to split the statement into two cases: if x is an even number, or if x is an odd number.

Case 1: If x is even, then \textcolor{red}{x=2n} for some integer n.

Then,

\begin{aligned} f(2n) &= 3(2n)^2+3(2n)-2 \\ &= 12n^2 + 6n - 2 \\ &= 2(6n^2+3n-1) \end{aligned}

n is an integer, therefore 6n^2+3n-1 is an integer.

Hence, 2(6n^2+3n-1) is an even integer.

So, f(x) is even when x is even.

 

Case 2: If x is an odd number, then \textcolor{blue}{x = 2m+1} for some integer m.

Then,

\begin{aligned} f(2m+1) &= 3(2m+1)^2 + 3(2m+1) - 2 \\ &= 12m^2 + 12m + 3 + 6m + 3 - 2 \\ &= 12m^2 + 18m + 4 \\ &= 2(6m^2 + 9m + 2) \end{aligned}

m is an integer, therefore 6m^2 + 9m + 2 is an integer.

Hence, 2(6m^2 + 9m + 2) is an even integer.

So, f(x) is even when x is odd.

 

Hence, f(x) is even for any integer x, and the statement is true.

A LevelAQAEdexcelOCR

Skill 4: Disproof by Counter-Example

To disprove a statement by a counter-example, all you need to do is show that the statement is false for one case.

Example: Disprove the following statement:

“For any pair of real numbers x and y, if x^2=y^2 then x=y

 

We only need to find one set of values such that the statement is false.

For example, take x=3 and y = -3

Then,

x^2 = 3^2 = 9 and y^2 = (-3)^2 = 9

So, \textcolor{limegreen}{x^2 = y^2}

However, \textcolor{red}{x \neq y}, and so the statement is not true.

A LevelAQAEdexcelOCR

Proof Example Questions

Question 1: Write out the following sets as lists of elements:

a) \{x:x^2=16\}

b) \{\text{factors of 18}\}

[2 marks]

A Level AQAEdexcelOCR

a) \{ -4, 4\}

b) \{1,2,3,6,9,18\}

MME Premium Laptop

Save your answers with

MME Premium

Gold Standard Education

Question 2: Is the following statement true or not?

“For any pair of real numbers x and y, x^2+y^2>0

Give either a proof or a counter-example.

[3 marks]

A Level AQAEdexcelOCR

We only need to give one case for a counter-example, if it is false.

The only case in which the statement isn’t true is when x=0 and y=0. This gives 0^2+0^2=0, and clearly 0 is not greater than 0

MME Premium Laptop

Save your answers with

MME Premium

Gold Standard Education

Question 3: Prove that the sum of two rational numbers is rational.

[4 marks]

A Level AQAEdexcelOCR

Take any two rational numbers, and call them a and b

By definition of rational numbers, a can be written in the form a = \dfrac{p}{q} and b = \dfrac{r}{s}, where q and s are not 0.

 

Then either:

\dfrac{p}{q} + \dfrac{r}{q} = \dfrac{p+r}{q} if the denominators are the same

 

\dfrac{p}{q} + \dfrac{r}{s} = \dfrac{ps + qr}{qs} if the denominators are different

 

ps, qr and qs are all products of integers, so they must also be integers.

p+r and ps + qr are all sums of integers, so they must also be integers.

Since q and s are both non-zero, qs must also be non-zero.

Hence, \dfrac{p+r}{q} and \dfrac{ps + qr}{qs} are rational numbers.

Therefore, a+b must be rational.

So, the statement is true.

MME Premium Laptop

Save your answers with

MME Premium

Gold Standard Education

Question 4: Prove that the sum of any 3 consecutive even numbers is always a divisible by 6.

[3 marks]

A Level AQAEdexcelOCR

By definition, three consecutive even numbers are 2n, (2n+2) and (2n+4).

Adding them together gives,

 

2n+(2n+2)+(2n+4)=6n+6 = 6(n+1)

 

n+1 is an integer, so 6(n+1) is divisible by 6

MME Premium Laptop

Save your answers with

MME Premium

Gold Standard Education

Question 5: Prove that n^2 - 2n > 2, for all integers in the interval 3 \leq n \leq 6

[2 marks]

A Level AQAEdexcelOCR

We need to prove by exhaustion that the statement is true for all integers in the interval 3 \leq n \leq 6

 

n=3:   3^2 - 2(3) = 3 > 2

n=4:   4^2 - 2(4) = 8 > 2

n=5:   5^2 - 2(5) = 15 > 2

n=6:   6^2 - 2(6) = 24 > 2

 

Hence, the statement is true.

MME Premium Laptop

Save your answers with

MME Premium

Gold Standard Education

Additional Resources

MME

Exam Tips Cheat Sheet

A Level
MME

Formula Booklet

A Level

Proof Worksheet and Example Questions