Methods of Proof for Every Occasion
Three essential proof techniques, followed by many not-so-essential
Most people may think that mathematics is about doing hard sums with large numbers. Whilst it is true that you can do seriously hard computations all day long (try computing the integral of the square root of tan), the majority of mathematics is based on proofs.
Here I will outline some of the most common methods of proving a statement (and some of the funnier ones). For each method I will try and give a simple example of a proof using that method.
The method of direct proof uses logical steps to achieve the desired result. These logical steps can be axioms, definitions, and previously proved propositions.
For example: the sum of two even integers is an even integer.
We consider two even integers m, n. They are even so can be written as m=2a, n=2b, for some integers a and b (this is by definition of being an even integer). Then the sum m+n=2a+2b, which we can write as 2(a+b). Since a+b is an integer, we can conclude that 2(a+b) is even and therefore m+n must be even. QED.
Proof by Contradiction
In essence, you assume the opposite and then try to derive some contradiction. The idea is that if assuming something leads to a contradiction, then that original assumption must be false.
This proof is usually useful in trying to prove the uniqueness of something. I look to group theory for an example: Prove there is a unique identity element.
Suppose the contrary: let there be two distinct elements e and e’ (e≠e’) that have the property that e·x = x·e = x and e’·x = x·e’ = x for all x in the group. Consider e·e’. By definition of identity, we can argue that e·e’ = e and also e·e’=e’, therefore e=e’ which is a contradiction to our initial assumption. Therefore, the identity element must be unique. QED
Proof by Induction
If we want to prove that some proposition holds for all integers, then induction can be a good way to go. The idea is that you prove the proposition for a base case (say n=0). Then you assume the proposition to hold for some n, then use that to prove that it must hold for n+1. The hand-wavy reason this works is that since it holds for 0, it must then hold for 1, since it holds for 1, it must hold for 2, etc…
Granted, I see this one less and less, but used it very often when proving things in high-school.
The sum 0+1+…+k = k(k+1)/2.
Base Case: k = 0. The left hand side is 0 and setting k=0 on the right hand side, we see that k(k+1)/2 = 0. Therefore the base case holds.
Inductive step: Now assume that the above statement holds for k=n for some integer n.
Now we want to show that it holds for k=n+1. On the left hand side, we have 0+1+…+n+(n+1) = n(n+1)/2 + (n+1). This holds by our inductive assumption. We can now write it as n(n+1)/2 + (n+1)=(n+1)((n+1)+1)/2 which is exactly the statement for the proposition when k=n+1.
Therefore since the proposition holds for k=0, and if k=n is true then k=n+1 is true, then the above proposition holds for all integer values of k. QED
There are more methods that you will encounter along the way when studying and reading mathematics, but the three above will get you most of the way. If those fail then here are some other methods which remain tried and tested methods:
Proof by Authority
“I am telling you this is true”
Proof by Gaussian Authority
“Gauss said it is true, therefore it must be”
Proof by Triviality
“The proof is trivial, so I leave it as an exercise to the reader”
Proof by Delayed Triviality
“The proof is trivial. ” At this point, a student puts up their hand and asks if it is indeed trivial. The lecturer leaves for 30 minutes, when they return:
“Yes, it indeed is trivial”
Proof by Plausibility
“It looks like it should be true, so let us assume it is”
Proof by Dense Notation
“Let us assume …” Then over the course of the next 5 hours, fills up 20 blackboards with 4 different alphabets “And therefore the abc conjecture holds.”
Proof by Inaccessible Reference
“The proof can be found on page 845 of the 687 page book”
“Proof can be found in a private memoir of the Hungarian Mathematical Society in 1898, the only remaining copy can be found in the basement of Béla Bollobás (untranslated)”
Proof by Deferred Reference
“The proof may be found in my upcoming paper”
It is often noted that the upcoming paper is not so upcoming as once thought.
Proof by Circular Reference
“The proof for theorem 12 follows directly by theorem 15.
The proof for theorem 15 follows directly by theorem 12.”
Proof by Assumption of RH
“Assume the Riemann Hypothesis…”
Proof by Hand Waving
Proof by Vigorous Hand Waving
For when hand waving was not sufficiently convincing
Proof by Overwhelming Evidence
“We have checked several billion integers and haven’t found a counterexample yet”
Proof by Insufficient Margin Width
“I have discovered a truly marvellous proof of this, which this margin is too narrow to contain.”
Proof by …
The remaining methods of proof are left as an exercise to the reader. ■