"...the use of the word exhaustion means that the proof 'exhausts all possibilities', it 'considers completely all possible options'."

Sadler, A. (2016). Mathematics specialist. Student book. Units 1 & 2. South Melbourne: Cengage Learning Australia.

Method of exhaustion, in mathematics, technique invented by the classical Greeks to prove propositions regarding the areas and volumes of geometric figures. Although it was a forerunner of the integral calculus, the method of exhaustion used neither limits nor arguments about infinitesimal quantities. It was instead a strictly logical procedure, based upon the axiom that a given quantity can be made smaller than another given quantity by successively halving it (a finite number of times). From this axiom it can be shown, for example, that the area of a circle is proportional to the square of its radius. The term method of exhaustion was coined in Europe after the Renaissance and applied to the rigorous Greek procedures as well as to contemporary “proofs” of area formulas by “exhausting” the area of figures with successive polygonal approximations.

• Method of exhaustion. (2021). In Encyclopædia Britannica. Retrieved from https://school.eb.com.au/levels/high/article/method-of-exhaustion/33426

Many theorems state that a specific type or occurrence of an object exists. One method for proving the existence of such an object is to prove that P ⇒ Q (P implies Q). In other words, we would demonstrate how we would build that object to show that it can exist. A proof by construction is just that, we want to prove something by showing how it can come to be. There are only two steps to a direct proof :

1. Assume that P is true.

2. Use P to show that Q must be true.

Let’s take a look at an example.

Theorem: If a and b are consecutive integers, the sum of a + b must be an odd number.

Following the steps we laid out before, we first assume that our theorem is true. We then can say that since a and b are consecutive integers, b is equal to a + 1. In that case, a + b can be rewritten as a + a + 1 or 2a + 1. Therefore, we can say that a + b = 2k + 1. We know that any number multiplied by an even number must be even. We also know that if we add 1 to any even number, it becomes odd. Given these, we can say: a + b = 2k + 1 shows that a + b is odd.

"Proof by induction is like an 'infinite ladder'.

If we can prove that 

• if any rung exists then the next rung must also exist,

and that

• at least one rung does exist,

then the inifinite ladder must exist." (Saddler, 2016)

For example, we may want to prove that 1 + 2 + 3 + … + n = n (n + 1)/2.

In a proof by induction, we generally have 2 parts, a basis and the inductive step. The basis is the simplest version of the problem, In our case, the basis is,

For n=1, our theorem is true

since, 1 = 1(1 + 1)/2 .

The next part of the proof is the inductive step. The inductive step is the part where to generalize your basis and take it a step further.

Suppose our theorem is true for some n = k ≥ 1, that is:

1 + 2 + 3 + . . . + k = k(k + 1)/2.

Prove that our theorem is true for n = k + 1, meaning:

1 + 2 + 3 + . . . + k + (k + 1) = (k + 1)(k + 2) 2 .

This is the core of the inductive step. We take our theorem, generalize it and take it to the next step. We added in the (k + 1) on the left side of the equals sign and we changed the k on the right side of the equals sign to (k + 1)(k + 2). We finally finish off our proof with

And with that, we’re done. We’ve followed a logical progression from the basis or the base case, to the inductive step, all the way through to the final part of the proof.

A common form of proving a theorem is assuming the theorem is false, and then show that the assumption is false itself, and is therefore a contradiction.

Let’s take a look at a simple example:

Theorem: If n² is even, then n is even.

Given this theorem, let’s assume that n² is even but n is odd. We’re assuming that the theorem is false. As we showed in the previous section, an odd number can be characterized by n = 2k + 1. Using that definition for an odd number we say the following:

n² = (2k + 1)² = 4k²+ 4k + 1 = 2(2k² + 2k) + 1

Or more concisely, n² = 2(2k² + 2k) + 1. If we let m = 2k² + 2k, we get n² = 2m + 1. Using the definition for odd numbers that we mentioned before, we must say that n² is odd. In our assumption, we declared n² to be even. A contradiction! Since our assumption cannot be, then n² must be even, and we’ve proven the original theorem.