Proof by Exhaustion

Proof by Exhaustion is the proof that something is true by showing that it is true for each and every case that could possibly be considered. This is also known as Proof by Cases – see Example 1 in the Proof by Deduction Examples lesson. This is different from Proof by Deduction where we use algebraic symbols and construct logical arguments from known facts to show that something is true for all numbers. For the case of Proof by Exhaustion, we show that a statement is true for each number in consideration (or subsets of numbers). Proof by Exhaustion also includes proof where numbers are split into a set of exhaustive categories and the statement is shown to be true for each category. Proof by Deduction can then be used within the categories – see Example 2 in the Proof by Deduction Examples lesson. In addition to the rules listed in the Proof by Deduction Notes, it is worth memorising the following sets of numbers:

  • {\mathbb N} = \left\lbrace 1,2,3,4,5,...\right\rbrace is known as the set of natural numbers. It is the set of all positive integers.
  • {\mathbb Z} = \left\lbrace ... -3, -2, -1, 0, 1, 2, 3,...\right\rbrace is the set of all integers including those that are negative and 0. Note that the positive part is sometimes denoted {\mathbb Z}^+ which, of course, is simply {\mathbb N}.
  • {\mathbb Q} is the set of all rational numbers – these are numbers that can be represented as fractions and includes recurring decimals.
  • {\mathbb R} is the set of all real numbers. This includes irrational numbers such as e or \pi but does not include the square root of negative numbers (these are known as imaginary numbers).

Examples

Prove that (n+1)^3\geq 3^n for n\in{\mathbb N}, n\leq 4.

Solution:

We must show that (n+1)^3 is greater than 3n for all n that is a natural number less than or equal to 4. The natural numbers less than or equal to 4 includes 1, 2, 3, and 4. Hence, proving the above by exhaustion will involve showing that it is true for n set equal to 1, 2, 3 and 4 successively:

  1. For n=1, (n+1)^3=(1+1)^3=2^3=8 and 3^n=3^1=3. Since 8\geq 3, the above is true when n=1.
  2. For n=2, (n+1)^3=(2+1)^3=3^3=27 and 3^n=3^2=9. Since 27\geq 9, the above is true when n=2.
  3. For n=3, (n+1)^3=(3+1)^3=4^3=64 and 3^n=3^3=27. Since 64\geq 27, the above is true when n=3.
  4. For n=4, (n+1)^3=(4+1)^3=5^3=125 and 3^n=3^4=81. Since 125\geq 81, the above is true when n=4 and thus concluding the proof by exhaustion.

Note that n=5 is the first instance when the statement breaks down.

Prove that every perfect cube number is a multiple of 9, one less than a multiple of 9 or one more than a multiple of 9.

Solution:

Trick: Every integer n is a multiple of 3 (n=3m), one less than a multiple of 3 (n=3m-1) or one more than a multiple of 3 (n=3m+1). Consider n=3m, then n^3=(3m)^3=27m^3=9\times 3m^3 which is a multiple of 9. Now consider n=3m-1, then n^3=(3m-1)^3=27m^3-27m^2+9m-1=9\left(3m^3-3m^2+m\right)-1 which is one less than a multiple of 9. Finally consider n=3m+1, then n^3=(3m+1)^3=27m^3+27m^2+9m+1=9\left(3m^3+3m^2+m\right)+1 which is one more than a multiple of 9 and concluding the proof by exhaustion. Note that this is proof by exhaustion since the proof is split into cases that exhaust all possibilities – proof by deduction is then used within each case consideration. 

Videos

https://youtu.be/ijKO9-mOT2o

A detailed Proof by Exhaustion example showing that all square numbers are either a multiple of 4 or one more than a multiple of 4.

https://youtu.be/1V_t1LZgg-E

Another example of Proof by Exhaustion, slightly more involved than the previous video, showing that all square numbers are either a multiple of 3 or one more than a multiple of 3.

Extra Resources

proof by exhaustion

Take the mathematical proof test – a selection of exam style questions on Proof by Deduction, Proof by Exhaustion and Disproof by Counterexample.

Take the test now.

AS Maths Proof

A2 Maths Proof