User:Temperal/The Problem Solver's Resource Proofs

Introduction \| Other Tips and Tricks \| Methods of Proof \| You are currently viewing the methods of proof section..

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. Please note that most material on this page is relatively simple; this section is only for introducing beginners to new techniques. If one wishes to improve at more advanced problem solving, solving problems is recommended.

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 Problem 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 $p_1, p_2, p_3,...p_n$ where $p_1<p_2<p_3...<p_n$ . If we can find another prime number that is greater than $p_n$ , we will have disproved our assumption. Consider the number $p_1p_2p_3...p_n+1$ . 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 $p_n$ so we have found a new prime number. This violates our assumption, so there must be an infinite number of primes.

Example Problem 2

Prove that $\sqrt{2}$ is irrational. (Also a very classic question)

Solution

The assumption should be fairly obvious here. We assume that $\sqrt{2}$ is rational. From the definition of rational numbers, $\sqrt{2}$ can then be written as a fraction in lowest terms. Let $\sqrt{2}=\frac{p}{q}$ , where p and q are relatively prime. Squaring and multiplying by $q^2$ , we have $2q^2=p^2$ . As 2 divides the left hand side, it must also divide p (a very common example of divisibility being helpful). Let $p=2r$ ; then $2q^2=4r^2\rightarrowq^2=2r^2$ (Error compiling LaTeX. Unknown error_msg). By the same argument as last time, we let $q=2s$ . However, now we have $\sqrt{2}=\frac{p}{q}=\frac{2r}{2s}=\frac{r}{s}$ . Recall though, that we stated that p and q were relatively prime. Now, we see that both are divisible by 2. This contradicts our original assumption, so $\sqrt{2}$ must indeed be rational.