MA 323A Combinatorial Geometry!

Notes on How to do Proofs!

Hey! The following are brief notes on the various techniques on how to prove things. This is basically a review of the proofs you learned in Discrete Math, so you might want to look back at your Discrete Math textbook for help.

Basics

Firstly, every theorem that you encounter will be of the form IF .... blah blah ... THEN ... bleh bleh.

The "blah blah" part is called the hypothesis and the "bleh bleh" is called the conclusion.

Direct Proof

This is the straight-forward way of proving things. You assume that the hypothesis is true and try to show, using logic, facts, and things we already know, that the conclusion is also true.

Example: Prove that the sum of two even numbers is always even.

If this were a problem, say, given to you in homework, then the first thing you should do is re-write it as an IF ... THEN ... statement. While you're at it, is can be a BIG help to give names to variables and such. Here's how I would do it:

Theorem: If x and y are two even integers then x+y is also even.
Proof: Assume the hypothesis is true, that is, let x and y be even numbers.
This means, by the definition of even integer, that x=2a for some integer a, and y=2b for some integer b. Therefore,
x + y = 2a + 2b = 2(a + b)
And look! 2(a + b) is satisfies the definition of being an even number! (That is, it's 2 times some integer.) Thus x + y is even, and the conclusion is true. Q.E.D.

Proof by Contradiction

This is a very useful proof technique. You prove something by contradiction by supposing that the theorem wasn't true and showing that this is impossible. In other words, if your theorem is an "IF p THEN q" statement, you want to suppose that this statement isn't true, which literally means that p must be TRUE and q must be FALSE. (Recall that this is the only way that the implication "IF p THEN q" can be false.)

Example: Prove that the sum of two even numbers is always even.

This time let's do a proof by contradiction! We set it up like we did before.

Theorem: If x and y are two even integers then x+y is also even.
Proof by contradiction: Assume the hypothesis is true. That is, let x and y be two even integers. Suppose, for the sake of contradiction, that x+y were not even. This means that x+y must be an odd number, since every integer is either even or odd. By the definition of what it means to be an odd integer, we have that x+y = 2c + 1 for some integer c.
Now, since x and y are even, we know that x=2a and y=2b for some integers a and b. Thus on one hand we have
x + y = 2a + 2b = 2(a + b) And on the other hand we have
x + y = 2c + 1 Therefore 2c + 1 = 2(a + b), which is impossible because an even number can't equal an odd number! Therefore our supposition that x+y was odd can't be true. Thus x+y must be even. Q.E.D.

Notice that the direct proof of this Theorem was a bit shorter. That doesn't always happen - sometimes a contradiction proof will be shorter. It just goes to show that it isn't always easy to find the "shortest possible" proof!

Proof by Contrapositive

In this proof technique you use the help of a bit of logical sneakery. Recall from what you learned in locig that the statement "IF p THEN q" is logically equivalent to the statement "IF not(q) THEN not(p)." Thus, if you prove one statement, then you've proven the other! And in some cases it's actually easier to prove "IF not(q) THEN not(p)."

Example: Given a graph with more than one vertex, show that if the graph is connected then it must have no vertices of degree zero.

This is pretty easy to prove directly, but let's see what a contrapositive proof would be like.

Proof by contrapositive: We are given a graph G with more than one vertex. Using the contrapositive, let us assume that G does have at least one vertex, v, of degree zero. (Thus, no edges are coming out of v.) We need to prove that G must not be a connected graph. (That is, we want to show that G is not all-one-piece.)
Since v has no edges coming out of it, it isn't connected to any other vertices in G. But we also know that G has more than one vertex! Thus there most be at least two disconnected components in G - one with v in it, all alone, and another component with other vertices in G. Thus G is not all-one-piece, and is disconnected. By the contrapositive, we have also shown that the original Theorem is also true. Q.E.D.

Proof by Exhaustion

This is a special kind of direct proof, where we break the possibilities down into several cases, and prove them one-by-one. We call it "exhaustion" because sometimes there are many cases and it can take a long time!

We will see an example of this when we prove that there are only 5 Platonic solids.

Proof by Induction

This is the classic "line up the dominoes, knock the first one down, and all the other dominoes will fall too!" style of proof. It can be very powerful when proving Theorems where some part of the statement is controlled by a positive integer. In particular, Theorems having to do with graphs have all sorts of integers in them! For example, you could try to do "induction" on the number of vertices in the graph. Or you could do induction on the number of edges.

To review, the basic Induction Principle is this:

Induction Principle: If P(n) is a statement with an integer parameter n and the following two conditions hold:

P(1) is true.
For n greater than or equal to 1, If P(n) is true then P(n+1) must also be true.

then P(n) is true for every positive number n.

Now, in Discrete Math you saw how to use induction to prove formulas, like this: 1 + 2 + 3 + 4 + ... + n = n(n+1)/2 But in this class we'll be using induction to prove more "abstract" things. Here's an example:

Pizza Example: Find the maximum number of pieces (not necessarilty equally sized) that you can cut a pizza into by using n straight cuts.

We'll talk about this in class, but here's the Theorem that this problem results in:

Theorem: If you make n straight cuts across a pizza, the most number of pieces the pizza will be cut into is n(n+1)/2 + 1.

Proof by induction: We'll be doing induction on the number of cuts, n.
The base case is when n=1, which cuts the pizza into two pieces, which satsifies the formula. Cool.
Now, for the induction step we will assume that the case P(n) is true, that is, we assume that if we make n cuts into a pizza then we can get n(n+1)/2 + 1 pieces.
We want to show that P(n+1) is true, that is, if we make n+1 cuts into a pizza then we can get (n+1)(n+2)/2 + 1 pieces.
OK, so we have the pizza, and we're about to make n+1 cuts to get the most pieces possible. First let's make n of the cuts, and by the induction hypothesis (IHOP) we know that this will give us a max of n(n+1)/2 + 1 pieces.
Now we want to make the n+1 cut, and we want it to create as many new pieces as possible. We will accomplish this if the n+1 cut crosses all of the previous n cuts in different places - that is, it doesn't cut through a point where two previous cuts meet. And if this cut crosses n other cuts, it will create n+1 new pieces, right? (It starts off cutting a single piece into two, then crosses a cut line, where it cuts a second piece in two, then crosses a second cut line, etc., until it crosses to the other side of the pizza, cutting the last piece it encounters in two. That's one more new piece made than the cuts it crossed. So if it crosses n cuts it'll make n+1 new pieces.)
In other words, we know that after making n+1 cuts the most number of pieces we can get is the number we got before plus n+1 new pieces. That is, number of pieces after n+1 cuts = n(n+1)/2 + 1 + (n + 1)
= n(n+1)/2 + n + 1 + 1 = ( n(n+1) + 2n + 2 ) / 2 + 1 = (n^2 + 3n + 2)/2 + 1
= (n+1)(n+2)/2 + 1 as desired! Therefore the Theorem is true by mathematical induction. Q.E.D.

Return to Combinatorial Geometry Page