Proof Techniques

Direct Proof #

Start at the hypothesis and walk to the claim.

A direct proof starts from the hypothesis and reaches the conclusion by steps that are each forced

A direct proof begins by writing what you are given in a form you can work with.

Each line follows from the one above by algebra, with nothing assumed on the way.

The last line matches the definition of even, so the claim is reached and the proof ends.

That is the whole method: assume the hypothesis, take forced steps, state the conclusion.

Now you

What does a direct proof never do?

A direct proof of "if n is odd then n² is odd" starts how?

Proof by the Contrapositive #

Prove the equivalent form that you can use.

Proving the contrapositive proves the original statement, and it is worth doing when the negated form is easier to work with

Starting from n² even leaves you nothing to write down, so a direct proof stalls here.

The contrapositive of the claim is true exactly when the claim is, so prove that instead.

Now the hypothesis is usable: n odd means n = 2k + 1, and squaring shows n² is odd.

Proving the contrapositive proves the claim. There is no extra step at the end.

Now you

After proving the contrapositive, what remains to be done?

Which claim is the contrapositive route best suited to?

Proof by Exhaustion #

Cover every case, and leave no case out.

Splitting a claim into a finite list of cases proves it only when the list leaves no case out

Choose a way of splitting that covers everything. Every whole number is even or odd.

Take the cases one at a time. With n even the expression comes out even.

With n odd it comes out even as well, so both cases land on the same answer.

The proof works only because the two cases together leave no whole number out.

Now you

A claim about n mod 3 is split into n = 3k and n = 3k + 1. What is wrong?

Both cases in a two-case proof reach the conclusion. What follows?

Disproof by Counterexample #

One failing case ends a claim about every case.

One case where a general claim fails disproves it, while any number of cases that fit proves nothing

A claim about every case is a universal statement, and it allows no exceptions anywhere.

The first forty values all come out prime. That is encouraging, but it is not a proof.

At n = 41 every term carries a factor of 41, so the value is 41 × 43, which is not prime.

One failure is enough. To disprove a claim about every case, a single counterexample is all you need.

Now you

Which one counterexample disproves the claim drawn?

The Pigeonhole Principle #

More objects than boxes forces a double.

When more objects than boxes are placed into the boxes, some box has to hold more than one

There are five objects and four boxes. Put one in each box and the boxes are full.

The fifth object has nowhere new to go, so some box ends up holding two.

How you arrange them never matters. More objects than boxes forces some box to hold at least two.

A long division has only so many remainders, so one must repeat and the decimal recurs.

Now you

Put 8 objects into 3 boxes. What is the largest number some box must hold?

A drawer holds socks in 6 colors, mixed up in the dark. How many must you take to be sure of a matching pair?

Proving Existence and Uniqueness #

Build one, then force any two to coincide.

Existence is proved by producing one such object, and uniqueness by forcing any two of them to be equal

An existence claim is settled by producing one object and checking it. Nothing more is needed.

Building the object is the usual way, and the construction is itself the proof.

For uniqueness, take any two that work and force them to be the same object.

Existence and uniqueness are separate claims. Producing one object says nothing about whether a second exists.

Now you

How is "there is a whole number whose square is 49" proved?

What does the phrase "there exists a unique n" claim?

Counting by a Bijection #

Match a hard count to an easy one, exactly.

Matching a hard collection one to one with an easy one proves the two have the same size

The ways of filling the jars are hard to count directly, because the coins are all alike.

Write the coins as stars and the walls between jars as bars, in one row.

Every row of stars and bars matches exactly one filling, and every filling matches exactly one row.

Counting the rows means choosing which 2 of the 9 places hold bars, so the answer is 36.

Now you

How many ways can 7 identical coins go into 4 labeled jars, empties allowed?

How many ways can 7 identical coins go into 3 labeled jars, empties allowed?