Types of Mathematical Proofs (2024)

A proof is a logical argument that tries to show that a statement is true. In math, and computer science, a proof has to be well thought out and tested before being accepted. But even then, a proof can be discovered to have been wrong. There are many different ways to go about proving something, we’ll discuss 3 methods: direct proof, proof by contradiction, proof by induction. We’ll talk about what each of these proofs are, when and how they’re used.

Before diving in, we’ll need to explain some terminology.

A theorem is a mathematical statement which is proven to be true.

A statement that has been proven true in order to further help in proving another statement is called a lemma.

Now that we’ve gotten that out of the way, let’s job into some types of proofs!

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.

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.

Proof by induction is a more advanced method of proving things, and to be honest, something that took me a while to really grasp. This method is used to show that all elements in an infinite set have a certain property. 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.

We looked at a few different types of proofs and how they really work. We can use these methods to make logical arguments about the validity of some statement in everyday life, or in the code that we right, or in countless of other situations.