What is a proof?

A written proof is a one-way conversation between the writer and the reader. This conversation takes place in English. To save space and time, mathematical symbols may be used to stand for words, but each mathematical symbol has a fixed, conventional word (or small set of words) that it is allowed to substitute for; you are not free to make up your own (unless you explicitly state what you are defining your symbols). For example, ``='' stands for ``equals'', ``which equals'', or ``is equal to''; it does not stand for ``Doing the next step in this problem, I arrive at the expression I'm writing to the right of the equals sign''. Your written work should have the property that, when the conventional meanings of your symbols are substituted for the symbols themselves, the result is a collection of sentences, with correct grammar and punctuation, detailing the logical flow of the argument.

When you see someone else's final proof, it may appear that he or she has pulled something out of thin air. This is a common misunderstanding of what's being asked in ``show'' and ``prove'' problems. Your approach to any such problem involves some thought process which hopefully will lead you to an answer (i.e. a proof). As far as the thought process goes, anything is valid---you can work backwards, make leaps of faith, make mistakes, etc. This is all okay because at this stage you are not claiming to have an answer. All you are doing is trying to collect facts and ideas that you will later assemble into an answer. This thought process is not what you are being asked to write down; you are only being asked to write down the final proof. When you write this down correctly, you are showing two things: (i) that you recognize what a valid proof is, and (ii) in all likelihood, you came upon your proof by an intelligent thought process, because the chance that you just stumbled onto a correct proof by pure luck is very small.

There is no single method guaranteed always to lead you to a proof, but here are a couple of methods that work well in certain problems:

• If you're instructed ``Show that this thing here is a widget'', usually what you have to do is write down the definition of widget and check that this thing here meets all the criteria of the definition. If the problem reads ``Show that this thing here is a widget'', you have to exhibit a property of widgets that this thing here lacks.

• In many instances, proof by contradiction works. The logic is as follows. You are asked to prove ``If P is true, then Q is true.'' Start by assuming that P is true but Q is false . If, after a series of logical deductions, you reach a contradiction, then the assumption that Q is false in the presence of P being true must be wrong, and hence Q must be true whenever P is true. For an example, see Example 2 below (the part labeled ``valid proof'').

• Sometimes proof by induction works. This potentially applies when you are trying to prove something that can be expressed that a collection of statements S_n is true for every positive integer n (or for every integer greater than or equal to whatever integer labels the first statement). Proof by induction proceeds by first showing that S₁ is true, and then showing that whenever n is such that S_n is true (called the ``inductive hypothesis''), then S_n+1 is true. This proves what's wanted, because then S₁ true implies S₂ true, which implies S₃ true, which implies S₄ true, etc.
  Example. Prove that for all integers n greater than or equal to 1, the sum of the first n positive integers is n(n+1)/2.

  Proof: Let S_n be the statement that the sum of the first n positive integers is n(n+1)/2. S₁ asserts that 1=1(1+1)/2, which is true. Suppose that n is such that S_n is true. Then the sum of the first n+1 natural numbers is n(n+1)/2+(n+1) = (n+1)(n/2 +1) = (n+1)(n+2)/2, so S_n+1 is true. This completes the proof.

Other times, to find proofs you have to struggle to understand why something is true. Experience and thorough knowledge of examples aere your best friends here. Another approach is to try to look for a counterexample of what you're being asked to prove. You should be able to find a reason why each of your attempted counterexamples fails.

Some common mistakes in proofs.

• ``Proof'' by lack of contradiction (not to be confused with the valid method proof by contradiction). In this method, you start by assuming what was supposed to be your conclusion as your hypothesis, and then say that you're finished when you reach no contradiction. Here is an example.

  Example 1. Given that the total number of points scored in a certain Gator football game was 80, prove that the Gators scored 73 and their opponents scored 7.

  `` Proof: '' 73+7=80.

  That we reached no contradiction shows only that the conclusion is consistent with the hypothesis, not that it follows from the hypothesis. In fact, what the argument actually proves is exactly the converse of what we were supposed to prove (it proves that if the Gators scored 73 and their opponents 7, then the total number of points scored was 80, not the other way around).

  This brings us to the next type of mistake, closely related to the first.

• Proving the converse of what you are supposed to prove.

  The converse of a statement ``if P then Q'' (or ``if P is true then Q is true'') is the statement ``if Q then P''. You cannot prove that ``if P is true then Q is true'' by starting with the assumption that Q is true, and then deducing that P is true! This is deducing the hypothesis from the conclusion, not the other way around.

• ``Proof'' by simply asserting that what you are asked to prove is true.

  Example 2. Show that if m and n are odd integers, then m+n is even.

  ``Proof:'' We know that the sum of two odd integers is even. Hence if m and n are odd, m+n is even.

  In this argument, the first sentence merely re-states in different words what was supposed to be proved. No logical path from hypothesis to conclusion is given.

• Starting a proof with an unconditional assertion of what you are supposed to be proving. This is a common mistake when you are asked to prove two mathematical expressions are equal. See ``Proving the converse of what you are supposed to prove'' above.

• ``Proof'' by example. Suppose you are given the problem ``Show that every even positive integer greater than two is the sum of two prime numbers.'' You observe that 4=2+2, 6=3+3, 8=3+5, 10=3+7, 12=5+7, 14=7+7, 16=5+11, 18=5+13, 20=7+13, etc. You list example after example. That still doesn't mean there isn't some even number you haven't listed that isn't the sum of two primes.

  Here's another instance: ``Prove that if n is prime, then 2^n-1 is prime''. You start checking: 2²-1=3 is prime, 2³-1=7 is prime, 2⁵-1=31 is prime, 2⁷-1=127 is prime. You might now think the statement is true. But 2¹¹-1=2047= 23 x 89 is not prime. The statement you were told to prove is actually false!

• ``Proof'' by notation. For example, you can't prove that addition of matrices is commutative by saying that since a + sign is used, the operation must be commutative.

• ``Proof'' by lack of imagination. ``I don't see how the theorem can possibly be false, so it must be true.'' Alternatively, ``I don't know a counterexample, so the theorem must be true.''

• Writing all the correct steps for a proof, but writing them in an invalid order. (This is sometimes how people end up proving the converse of what they were supposed to prove.)

• Assuming the reader can read your mind even if what you wrote does not make sense in English or means something wrong.