Proof Decisions

We need to decide when each proof type should be used!

Induction, Direct, Contradiction, Contrapositive

These topics were discussed in week 4. Be sure to revisit this week briefly, and think about these clues when reading about these other proof types.

Combinatorial Proofs

Combinatorial proofs are almost exclusively used for counting problems. This is a good thing! If we see a combinatorial identity, that is, one with combinations, permutations, or other cues, we can think about using a combinatorial proof.

Pidgeonhole Principle

Pidgeonhole proofs are also relatively simple to find. They have a specific structure, so pay attention to what is to be proved. If it is analagous to shoving pigeons into boxes, then it is likely fine to use pigeonhole principle.

Construction

Proofs by construction often fall under the category of direct proofs. If you see some indications that a direct proof might be the way to go, or if you think creating an example would help your proof, then proof by construction might be the way to go. Just be careful that you are not just using an example as a proof.

Which Proof to Use?

There are many, many proof types, and frankly, the best way to really understand which proof type to use is by looking at proofs and practicing your own.

The truth is that many things can be proved multiple ways as well. It's just a matter of what you think will be easiest. View the video below showcasing a number of ways to prove the simplest arithmetic series.

If you go to this video on youtube, there are even more proofs in the comments!

Think about it: Which proofs were truely nice for this problem? That is, which ones were easy to understand and efficient?