how to be good at proving?

Question

I'm starting my Discrete Math class, and I was taught proving techniques such as proof by contradiction, contrapositive proof, proof by construction, direct proof, equivalence proof etc.

I know how the proving system works and I can understand the sample proofs in my text to a sufficient extent. However, whenever I tried proving on my own, I got stuck, with no advancement of ideas in my head. How do you remedy this solution? Should i practise proving as much as possible?

So far I've been googling proofs for my homework questions. But the final exam got proving questions (closed-book) so I need to come up with the proofs myself.

We mainly focus on proving questions related to number theory. Should I read up on number theory and get acquainted with the properties of integers? I don't know how I should go about becoming proficient in proving. Can you guys share your experience on overcoming such an obstacle? What kind of resources do you use for this purpose?

Thank you!

Answer 1

I do not consider myself "good" at proving things. However, I know that I have gotten better. The key to writing a proof is understanding what you are trying to prove, which is harder than it may seem.

Know your definitions. Often, I have been hampered or seen students hampered by not really knowing all of the definitions in the problem statement.

Work with others. Look at what someone else has done in a proof and ask questions. Ask how they came up with the idea, ask that person to explain the proof to you. Also, do the same for them. Explain your proofs to a classmate and have them ask you questions.

Try everything. Students often get stuck on proofs because they try one idea that does not work and give up. I often go through several bad ideas before getting anywhere on a proof. Another good strategy is to work with specific examples until you understand the problem. Plug in numbers and see why the theorem seems to be true. Also, try to construct a counterexample. The reason counterexamples fail often leads to a way to prove the statement.

Answer 2

While you mention proof methods, what you seem to need are proof-finding strategies. That's a large field. Here are just a few hints:

• Make yourself acquated with the premises. How can the statement fail if a single premise is left out?
• Find yourself a specific numerical example of the problem statement and check the conditions. Maybe you note a way how the premises enforce the validity of the statement for this example.
• Try to find a counterexample. You (probably) won't find one, but you might notice what kind of obstacles prevent you from finding it.
• Check extremes. If the statement says "For all real numbers with $0<r<2$ ...", then check what would happen with $r=0$ and $r=2$

Answer 3

Practice, Practice, Practice!

Get books in the class you are doing, review the proofs. Learn to look at a theorem and see if you can figure out a proof approach.

There are also books that may help along these lines with general proof approaches.

General Proof Strategies How to Solve It: A New Aspect of Mathematical Method (Princeton Science Library) [Paperback] G. Polya (Author)

How to Prove It: A Structured Approach [Paperback] Daniel J. Velleman (Author)

The Nuts and Bolts of Proofs, Third Edition: An Introduction to Mathematical Proofs [Paperback] Antonella Cupillari (Author)

How to Read and Do Proofs: An Introduction to Mathematical Thought Processes [Paperback] Daniel Solow (Author)

Discrete Math http://www.cs.dartmouth.edu/~ac/Teach/CS19-Winter06/SlidesAndNotes/lec12induction.pdf Discrete Mathematics with Proof [Hardcover] Eric Gossett (Author)

Discrete Mathematics: Mathematical Reasoning and Proof with Puzzles, Patterns, and Games [Hardcover] Douglas E. Ensley (Author), J. Winston Crawley (Author)

Schaum's Outline of Discrete Mathematics, Revised Third Edition (Schaum's Outline Series) by Seymour Lipschutz and Marc Lipson (Aug 26, 2009)

2000 Solved Problems in Discrete Mathematics by Seymour Lipschutz (Oct 1, 1991)

Concrete Mathematics: A Foundation for Computer Science (2nd Edition) by Ronald L. Graham, Donald E. Knuth and Oren Patashnik (Mar 10, 1994)

Finite and Discrete Math Problem Solver (REA) (Problem Solvers Solution Guides) by The Editors of REA and Lutfi A. Lutfiyya (Jan 25, 1985)

The problem books above would also be useful references for working problems and proofs.

HTH ~A

Answer 4

I second most of what the other answers have said, and would like to add a technique that I think is very useful for people first learning how to prove things:

If you are trying to "prove statement X," take the point of view that you are unsure if statement X is true. Then, try to decide if it is true or not. Seek counterexamples, as Hagen von Eitzen suggested. Seek evidence that might suggest X is true as well. If at some point you become convinced that X is actually false, great! Try to convince somebody else. If, on the other hand, you become convinced that X is true, great! However you became convinced can be the basis of your proof.

The heart of this piece of advice is: you need your proof-writing skills to be linked to the process by which you come to believe what's true and what isn't. Learning how to prove is nothing more than learning how to write down an absolutely convincing argument. Math has developed a lot of techniques, tricks, common argument patterns, etc., giving the impression that there is a whole body of stuff one has to master, but at its heart, a proof is nothing more than a logical argument that serves to convince everybody that something is true. To learn how to make good arguments, you need to be tuned into what is convincing and what isn't, and the authentic way to do this is to stay tuned in to what convinces you and what doesn't. So in trying to create a proof, the best thing is to take the point of view that you aren't sure if it is even true, and actually decide for yourself if and why you think it is, being as skeptical as you possibly can. If you become convinced it is true, no matter how skeptical you try to be, then whatever convinced you can be turned into your proof.

As an aside, I believe that those of us who are experienced at writing proofs have all, at least on some (conscious or unconscious) level, developed this habit of taking the point of view that we are not sure if it is true. Then we write the proof to convince ourselves.

Answer 5

First of all, I suggest you learn (and understand!) the definitions of the terms in the theorem. $\quad$

Then, try to understand what the theorem actually means. (This is the harder bit!) In the proof, check you have exhausted all the assumption (no theorem will have more assumptions than needed!).

If you can't prove a theorem using any of the usual methods (contrapositive, reductio ad absurdum, etc), "proof directly from the definitions" usually does the trick.

The only way to become good at proving theorems is to really understand what you are asked to prove!

Answer 6

Prove. ${}{}{}{}{}{}{}{}{}{}{}{}$

Answer 7

Watch Suits, the USA Network TV series. They continuously say you should "press where it hurts", and that's the exact thing you do in mathematics. The border cases are always interesting, and the conditions for a theorem are almost always where a proof starts. For example:

A continuous function $f:\mathbb{R}\to\mathbb{R}$ which is negative at 0 and positive at 1 (that is, $f(0)<0$ and $f(1)>0$) has a zero somewhere between 0 and 1.

What you should use to prove this theorem is that the function is continuous, that it is negative at 0 and that it is positive at 1. Now, first think about what these things really tell you: what does it mean for a function to be continuous, and how can you use negative and positive? Why wouldn't the theorem hold for noncontinuous functions? Can you give a counterexample if the function is continuous, but positive at both 0 and 1?

Such questions give you hints as to the reason the theorem is true, and might just lead you to a proof.

NB: they actually said something along the lines of "press until it hurts" instead of "press where it hurts", but it is a nice series nonetheless.