Proof Intuition and Faulty Proofs

Understanding proofs can become easy with enough practice. Creating proofs, and in particular, picking a proof style that will work well, can prove to be difficult.

Readings

Please read this first before moving on to the documents here on Anchor. As a reminder, and for reference, specific chapters are referenced at the beginning of the section for which they are relevant. Feel free to go back to the text(s), or review it if there's been a break since you last read the material. The readings on Anchor have some information in common with the text(s). This is to ensure you see the information from some different perspectives.

Applied Discrete Structures Chapter 3.9

Important Tools

Applied Discrete Structures Chapter 3.9

Remember: Please read the text linked above before reading the material below.

When starting on a proof there are important tools you will need to actually complete the proof.

Relevant definitions, theorems, and properties need to be found. Though first, you need to decide what may be relevant. This can be tricky for new students. How do you decide what tools you might need?

This requires some insight into the statement you wish to prove. In other words, you can't prove something without a decent knowledge of the related topics. At least, doing so would be difficult.

When looking at a statement you need to prove, consider what topics are involved. What words in the statement have mathematical definitions? Are there other ways to express some of these terms? Are there other statements you have seen or proved before that are related?

Once you have the tools, you can decide on the method.

Intuition

Developing an intuition for proofs is difficult and takes time. Here are some pointers for using a certain proof type, but you should work on developing your own.

Induction

As induction is recursive/iterative in nature, it works very well for sequences, including recurrence relations. This isn't to say induction only works for these topics, it can certainly work for others, but when proving a sequence's closed form, an inductive proof can be efficient.

Direct, Contrapositive, Contradiction

These three proofs consider different versions of $p \rightarrow q$. When deciding between these three, try writing the statement all three ways: $p \rightarrow q$, $\neg q \rightarrow \neg p$ and $\neg q \wedge p$. Once these are all written, sometimes it becomes obvious what version will work well for the problem.

If not, try starting each version. Can you think of the next step in any of these cases? Don't be afraid to switch methods if you find that the one you chose seems to be the wrong path, though you also shouldn't give up immediately if you cannot think of the next step.

Stepping away to take a break, then coming back to a proof problem can help give clarity. Reading out loud, or attempting to explain your thought process out loud can also help.

After enough practice, the choice of proof becomes intuitive, but it will take time and patience to get there.

Think about it: Start creating a list of indicators for each type of proof. You can start the list with the ideas above. Looking at the proofs done in this week's readings (both the textbook and the text on Anchor), are there other indicators? What are they? Continue to update this list as you write more proofs with your findings.