A typical math proof
What is a proof?
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!
Direct Proof (Proof by Construction)
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 Contradiction
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
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
Final solution for our proof
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.
Conclusion
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.
