Week 6: Prove it.

Well we're in clear proof territory now. The midterm behind us, it's now become all about proving this or that statement. It's a fairly fun process to be honest: a sort of puzzle that you fill in. We start with the corners - what we start with, and what we have to get to - and gradually connect them. Maybe there's fewer pieces than a puzzle: most proofs we do have around ten steps. We do, however, have more people working on each proof than would be tackling a puzzle.

What is neat about proofs is the step where you have to make the connection: where you're looking at the structure and considering, "What can I change to make this work?" I remember doing a lot of that in math in school, and it was always exhilarating when you came across a connection between the solution and the starting proof.

It's a skill that is really all intuition: you can't memorize it because proofs always vary in form. But there makes the dopamine rush all the better when you do discover the right way to proceed. What I've found, and what Prof. Heap is pushing towards, is that it nonetheless helps to have a few basic ideas to fiddle with the proof:

A. Transform
Transforming, i.e. rearranging the elements, either the end or the beginning can help. Using the contrapositive can often suggest a new way to proceed, or for more mathematical proofs, we can move the elements around.

B. Disprove
If it's not working, try the opposite: disprove it! And, if it's impossible to disprove, then you have a proof by contradiction.

C. Replace
I would often forget to consider this, but replacing elements with their equivalents is probably the best way to find the answer to a proof. If you can get rid of variables (starting to remind myself of optimization), then you are vastly simplifying the task at hand; if you replace a difficult variable with a simpler one, then you are vastly simplifying the task at hand. Be careful when doing this, of course. You don't want to make a mistake and mangle your proof. Use an appropriate replacement. One of which we've used several times has been replacing general even or odd integers n with a 2k or 2k+1, respectively. This can be really useful, and you should always consider it.

There's a few more ways to proceed: we talked about proof by cases and splitting up the proof on Friday, but these main three have been my standbys for a long time, and I recommend them. Share any methods you may have in the comments.