How to Prove It

This is just a quick guide I've come up with for tutoring students new to proofs. Without taking a mathematical reasoning class, many of my students have a lot of trouble writing correct proofs and using deductive reasoning as opposed to using intuition. Here's a quick overview of the types of proofs and how to think about them. 

How to Prove It

Approach

• Write what you are given and what you want to prove.
• Expand these into definitions: do not use intuition here, just write down the mathematical definitions of all terms.
• When starting your proof, only write the givens after the word “proof.” Do not confuse the goal with an assumption.
• Figure out what type of proof you’re doing:
• Direct Proof - Starts with definitions and proceeds to show conclusion using no new assumptions.
• Induction - When proving statements are true for all natural numbers, uses a base case and inductive step.
• Contradiction - Only used when a single statement is asked to be shown (e.g. show 2 is an irrational number) Assume the opposite, show a logical contradiction occurs.
• Contrapositive - Prove an “if p then q” statement by proving the logically equivalent statement: “if not q, then not p”. This is not the same as contradiction, since this method is used for conditional statements.
• Exhaustion - Also called proof by cases, where some property is needed to be proved, and all possible properties are tested. Occurs often in even/odd proofs since every natural number must be even or odd.
• Constructive - Showing a given system must have a certain property by attempting to generally construct the system, and showing the property is unavoidable.  

“Let” Statements

• Introduce your variables:

Let n be an even number.

Let q be a real number.

• Specify your variables: Give them the required properties.

Since n is even, n = 2p for some integer p.

Since x is a prime number, if x is the product of factors, they must be either 1 or x. In other words, x = a1a2...an implies ai = 1 or x for all i.

• Sometimes we may have to use i-sequences, as in the last example. If we want to talk about a sequence of any length, where we don’t care exactly how long it is, we can use i as an index, which typically goes from 1 to n.

Proof

• Now we start the actual proof. When writing the final version, proceed step by step making sure each step follows from the previous step. This sounds obvious, but it’s easy to look at the whole proof and start arguing from intuition.
• Intuition is helpful for planning proofs, but not for figuring out the details.
• Make sure you know the rule or theorem connected each statement to the previous, and state it clearly.
• Often you can leave these out, such as in “an even number n can be written as n = 2q for some integer q.” This should be followed by “by the definition of even numbers” but this is very obvious so we typically do not write it.
• If you use a theorem, be sure to state the name or full statement of the theorem, especially if you are using it in an indirect form.
• Do not say anything is obvious unless it really is obvious. Things often seem obvious from intuition that are false mathematically. Be precise.
• The final step in your proof should be that something implies the exact statement in your “to prove” section. Do not say “this is clearly the same as what we want to prove”. It must be exactly matching your definitions.

Things to Avoid!

• Never introduce variables in the middle of your proof, or in the middle of sentences. If you talk about a property of a number, give it a name.
• GOOD: An even number is an integer n such that n = 2q.
• BAD: An even number is an integer where n = 2q.
• BAD:  An even number is double another integer.
• If something breaks down into two cases, state that there are only two cases, and prove this. Suppose that there was a third case, what would it be?
• For example, “a number is either positive or negative” is incomplete: what if the number is zero?
• “A nonzero real number is positive or negative” is sufficiently obvious, and you do not need to prove why.
• Proving backwards: Sometimes proofs are much easier when you assume the goal and prove the conditions. This is proving the converse, which is a different and unrelated statement, so don’t do this.
• If you need to prove an “iff” statement (if and only if), consider this as two separate and unrelated proofs. Think of them individually and prove them as if they were individual problems.
• Note that “p iff q” means that p and q are equivalent, so it’s tempting to use some kind of “equivalence proof” where you show they represent the same thing. While this can sometimes work, it’s never wrong to just break it into two statements, and this has much less room for error.

Studying for Tests

• Make a list of all definitions of all terms, even if you think you know them. Be sure that you use mathematical definitions, not “intuitive” ones.
• Look over key theorems, prove them all from scratch. If you can’t get a proof right away, look at one line of solution then think more about it.
• When figuring out proofs, always think about it longer than you think you need to. If you give up, try harder for a little longer before looking at solution.
• Know which theorems you can state and which you’d need to prove. Most theorems stated in the textbook do not need to be proven on a test.
• Know the basic proofs. Many times professors will put one of the most basic theorems on a test to make you start from scratch to prove it. Practice a few of these.
• Be prepared to be introduced to something new on the test, such as new definitions or functions.

Resources

• How to Prove It - Polya (book)
• ProofWiki.org
• Math Stack Exchange (math.stackexchange.com)