Proof by Contradiction

Proof by Contradiction

A LevelAQAEdexcelOCRAQA 2022Edexcel 2022OCR 2022

Proof by Contradiction

You have already seen some types of proof, but there is one more which is a bit harder – proof by contradiction. There are different styles of questions in which you need to use proof by contradiction.

A Level AQA Edexcel OCR

Understanding Proof by Contradiction

A proof by contradiction assumes the statement is not true, and then proves that this can’t be the case.

Example: Prove by contradiction that there is no largest even number.

First, assume that the statement is not true and that there is a largest even number, call it \textcolor{blue}{L = 2n}

Consider \textcolor{blue}{L}+2

\textcolor{blue}{L}+2 = 2n+2 = 2(n+1)

which is also even and is larger than \textcolor{blue}{L}.

This is a contradiction to the original assumption, since there is an even number greater than the “largest even number”.

Hence, the statement is true.

A LevelAQAEdexcelOCR
A Level AQA Edexcel OCR

Example 1: Proving Surds are Irrational

Prove by contradiction that \sqrt{2} is irrational.

[5 marks]

Assume that the statement is not true, and so \sqrt{2} can be written as \dfrac{\textcolor{red}p}{\textcolor{blue}q}, where \textcolor{red}p and \textcolor{blue}q are both non-zero integers.

Also, assume that \textcolor{red}p and \textcolor{blue}q have no common factors.

Then,

\begin{aligned} \sqrt{2} &= \dfrac{\textcolor{red}p}{\textcolor{blue}q} \\ \textcolor{red}p &= \sqrt{2} \textcolor{blue}q \end{aligned}

If we square both sides,

\textcolor{red}p^2 = 2\textcolor{blue}q^2

Therefore, \textcolor{red}p^2 is an even number.

If \textcolor{red}p^2 is even, then \textcolor{red}p must be even also (you can prove this).

So, let \textcolor{red}p=2k for some integer k, and substitute this into the last step:

\begin{aligned} \textcolor{red}p^2 = (2k)^2 = 4k^2 &= 2\textcolor{blue}q^2 \\ 2k^2 &= \textcolor{blue}q^2 \end{aligned}

Therefore \textcolor{blue}q^2 is even and so \textcolor{blue}q is also even.

 

However, we assumed at the beginning that \textcolor{red}p and \textcolor{blue}q had no common factors, and since they are both even they must have at least one common factor. This contradicts our initial assumption.

Hence \sqrt{2} cannot be written as \dfrac{\textcolor{red}p}{\textcolor{blue}q}, so it is not rational.

Therefore, the statement is true.

A LevelAQAEdexcelOCR

Example 2: Proving that there are Infinitely Many Prime Numbers

Prove by contradiction that there are infinitely many prime numbers.

[5 marks]

Assume that the statement is not true in that there are a finite number of primes (n of them). Write them as

p_1, p_2, p_3, ... p_{n-1}, p_n

where p_1 = 2 and p_n is the largest prime number.

Multiply all of these primes together, and call it \textcolor{red}{N}:

\textcolor{red}{N = p_1 \times p_2 \times p_3 \times ... \times p_{n-1} \times p_n}

\textcolor{red}{N} is a multiple of every prime number in the list.

Now,

\textcolor{limegreen}{N+1} = \textcolor{red}{p_1 \times p_2 \times p_3 \times ... \times p_{n-1} \times p_n} + \textcolor{blue}{1}

\textcolor{limegreen}{N+1} should not be a prime number, since there are no prime numbers other than p_1, ... p_n.

If we divide \textcolor{limegreen}{N+1} by p_n, or any other prime p_i, this leaves a remainder of \textcolor{blue}{1}. Since there are no integers that divide \textcolor{blue}{1} other than 1 itself, \textcolor{limegreen}{N+1} must be a prime number, or be divisible by another prime greater than p_n.

This contradicts our original assumption.

Hence, there are infinitely many primes, and the statement is true.

A LevelAQAEdexcelOCR

Example Questions

Assume that the statement is not true, in that there is an even number n for which n^2 is an odd integer.

If n is even, then we can write n=2k for any integer k.

Then,

n^2 = (2k)^2 = 4k^2 = 2(2k^2)

which is even, since it is 2 \, \times a number.

However, this contradicts the assumption that there is an even number n for which n^2 is odd.

Therefore, if n^2 is an odd integer, then n must be odd, which proves the statement.

Assume that the largest multiple of 17 is 17n, where n is an integer. Call it L.

Then,

L+17 = 17n + 17 = 17(n+1)

which is a multiple of 17 and is larger that L.

This contradicts the assumption that L is the largest multiple of 17.

Hence, there is no largest multiple of 17, and so the statement is true.

Assume that there is an even number x such that x^3 is odd.

So, define x = 2k, where k is an integer.

Hence,

x^3 = (2k)^3 = 8k^3 = 2(4k^3)

Therefore, x^3 is even.

However, this contradicts the assumption that there is an even number x such that x^3 is odd.

Hence, if x^3 is odd, then x must be odd, which proves the statement.

 

Additional Resources

MME

Exam Tips Cheat Sheet

A Level
MME

Formula Booklet

A Level

Worksheet and Example Questions

Site Logo

Proof by Contradiction

A Level

You May Also Like...

A Level Maths Revision Cards

The best A level maths revision cards for AQA, Edexcel, OCR, MEI and WJEC. Maths Made Easy is here to help you prepare effectively for your A Level maths exams.

£14.99
View Product

A Level Maths – Cards & Paper Bundle

A level maths revision cards and exam papers for Edexcel. Includes 2022 predicted papers based on the advance information released in February 2022! MME is here to help you study from home with our revision cards and practise papers.

From: £22.99
View Product

Transition Maths Cards

The transition maths cards are a perfect way to cover the higher level topics from GCSE whilst being introduced to new A level maths topics to help you prepare for year 12. Your ideal guide to getting started with A level maths!

£8.99
View Product