User:Temperal/The Problem Solver's Resource Proofs

Methods of Proof

Many competitions involve only short answer or multiple choice questions, with no justification required. However, once you get to the elite, national competitions, mostly national olympiads, you suddenly are expected to justify your solutions. If you've never encountered problems where you must prove your results, you would most likely be overwhelmed. This page attempts to explain some of the most used techniques in writing proofs.

Contradiction

To many people, contradiction is one of the simplest methods of proof. In this technique, you attempt to prove the desired result in an indirect way. You first assume that the opposite result holds. Then, you attempt to find something that contradicts something that you already know or is given in the problem. Thus, you must've been wrong in assuming that the opposite result is true, so the only possible result is the one you wanted to prove!

Example 1: Prove that there are infinite primes. (This is an extremely classic and elegant proof)

Solution: Many new problem solvers are intimidated by a question that asks to prove anything relating to infinity. Hence, this seems like an excellent time to use contradiction, as we simply need to find a contradiction. Since our desired result is proving that there are an infinite amount of primes, it makes sense to assume that there are only a finite amount. Let the primes be where . If we can find another prime number that is greater than , we will have disproved our assumption. Consider the number . This number is not divisible by any of our known primes, so it itself must be prime. Also, it is evident that this number is greater than so we have found a new prime number. This violates our assumption, so there must be an infinite number of primes.