proof techniques

Proving things is an art, there is no mechanical way to do it. Like any other art one has to practice it to master it. One should get in the habit of asking why something is true/not true and then try to prove/disprove it.However, there are certain tricks/ways that can help shape the thinking when starting to think the proof.

For theorems of type, for All x: P(x)->Q(x)

Direct Proof:
We start with assuming that P(x) holds and then try to reach Q(x).

Proof by Contrapositive:
This proof technique uses the fact that contrapositive of p->q (which is -q->-p) has same truth value as p->q. So we can try to prove the contrapositive of original with direct proof technique.

Vacuous Proof:
If we can prove that P(x) is always false, then the statement p->q automatically becomes true.

Trivial Proof:
If we can prove that Q(x) is always true, no matter what.

For theorems of type, for all x: P(x)

Proof by Cases - Exhaustive Proof:
If x can only have a limited set of values, then we can apply P to *all* those values of x, if they all happens to be true(which has to be the case for theorem to be correct) then we have the proof.

Proof by Cases - Proof with limited Cases:
1. Some times, even though x can have a large(may be infinite) set of values but we can still use case techniue. For example let say P(x) is of the form of Q(sin(x)), then its enough to prove that P(x) holds for x E [0, PI], as sin(x) repeats itself for other values of x.
2. In cases something like x being real number, it is enough to show that P(x) holds for 3 cases which are.. x<0, x>0 and x=0

For theorems of type, there exists x | P(x)
It'll be enough to find just one value of x for which P(x) holds.

General
Proof by Contradiction:
With this technique, we start with the assumption that negation of the theorem statement is true and reach a contradiction.

Try to find counter-example:
For example if we were to prove a theorem of type, for all x:P(x); if we can find one value of x for which P(x) is false then we have disproved the theorem.

Proof by Induction:
Here we prove a base case, Make an inductive assumption and prove the incremental case. Way to increment has to be general enough that all the possible cases are covered.


Reference - Section 1.6 and 1.7 of Discrete Mathematics & Its Applications 6th Edition by Kenneth H Rosen.