logo20137

Proof by Exhaustion

In maths, proof by exhaustion means that you can prove that something is true by showing that it is true for each and every case that could possibly be considered. This is different to proof by deduction in that we do not use algebraic symbols to represent any number and showing that it is true for the symbol infers that it is true for all numbers – we must show that it is true for each number in consideration.

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

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 include 1, 2, 3, and 4. Proving the above by exhaustion will involve showing that it is true for 1, 2, 3 and 4:

  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.