Types of Proofs

Proof of Contruction

Proof by construction, or proof by example, is the construction of a concrete example with a property to show that something having that property exists. Joseph Liouville, for instance, proved the existence of transcendental numbers by constructing an explicit example.

Proof  by Contradiction

In proof by contradiction (also known as reductio ad absurdum, Latin for "by reduction toward the absurd"), it is shown that if some statement were so, a logical contradiction occurs, hence the statement must be not so. This method is perhaps the most prevalent of mathematical proofs. A famous example of proof by contradiction shows that is an irrational number:
Suppose that were a rational number, so by definition where a and b are non-zero integers with no common factor. Thus, . Squaring both sides yields 2b² = a². Since 2 divides the left hand side, 2 must also divide the right hand side (as they are equal and both integers). So a² is even, which implies that a must also be even. So we can write a = 2c, where c is also an integer. Substitution into the original equation yields 2b² = (2c)² = 4c². Dividing both sides by 2 yields b² = 2c². But then, by the same argument as before, 2 divides b², so b must be even. However, if a and b are both even, they share a factor, namely 2.


Proof by Induction


 A proof by induction is just like an ordinary proof in which every step must be justified. However it employs a neat trick which allows you to prove a statement about an arbitrary number n by first proving it is true when n is 1 and then assuming it is true for n=k and showing it is true for n=k+1. The idea is that if you want to show that someone can climb to the nth floor of a fire escape, you need only show that you can climb the ladder up to the fire escape (n=1) and then show that you know how to climb the stairs from any level of the fire escape (n=k) to the next level (n=k+1).


If you've done proof by induction before you may have been asked to assume the n-1 case and show the n case, or assume the n case and show the n+1 case. This is the same as what I'm explaining here but I will use a different letter because I think it avoids some confusion when trying to figure out what each case is.
 
Example 1: Prove 1+2+...+n=n(n+1)/2 using a proof by induction.
n=1: 1=1(2)/2=1 checks.