Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "User:Temperal/The Problem Solver's Resource Proofs"

(→‎Methods of Proof)
(skeleton)
Line 1: Line 1:
−
==Methods of Proof==
+
{{User:Temperal/testtemplate|the methods of proof section.}}
 +
==<span style="font-size:20px; color: blue;">Methods of Proof</span>==
 
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.
 
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==
+
===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!
 
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)
+
====Example Problem 1====
 +
Prove that there are infinite primes. (This is an extremely classic and elegant proof)
  
 +
=====Solution=====
 
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 <math>p_1, p_2, p_3,...p_n</math> where <math>p_1<p_2<p_3...<p_n</math>. If we can find another prime number that is greater than <math>p_n</math>, we will have disproved our assumption. Consider the number <math>p_1p_2p_3...p_n+1</math>. 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 <math>p_n</math> so we have found a new prime number. This violates our assumption, so there must be an infinite number of primes.
 
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 <math>p_1, p_2, p_3,...p_n</math> where <math>p_1<p_2<p_3...<p_n</math>. If we can find another prime number that is greater than <math>p_n</math>, we will have disproved our assumption. Consider the number <math>p_1p_2p_3...p_n+1</math>. 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 <math>p_n</math> so we have found a new prime number. This violates our assumption, so there must be an infinite number of primes.
  
−
Example 2: Prove that <math>\sqrt{2}</math> is irrational. (Also a very classic question)
+
====Example Problem 2====
 +
Prove that <math>\sqrt{2}</math> is irrational. (Also a very classic question)
  
−
Solution: Ok, the assumption should be fairly obvious here. We assume that <math>\sqrt{2}</math> is rational. From the definition of rational numbers, <math>\sqrt{2}</math> can then be written as a fraction in lowest terms. Let <math>\sqrt{2}=\frac{p}{q}</math>, where p and q are relatively prime. Squaring and multiplying by <math>q^2</math>, we have <math>2q^2=p^2</math>. As 2 divides the left hand side, it must also divide p (a very common example of divisibility being helpful). Let <math>p=2r</math>; then <math>2q^2=4r^2\rightarrowq^2=2r^2</math>. By the same argument as last time, we let <math>q=2s</math>. However, now we have <math>\sqrt{2}=\frac{p}{q}=\frac{2r}{2s}=\frac{r}{s}</math>. 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 <math>\sqrt{2}</math> must indeed be rational.
+
=====Solution=====
 +
The assumption should be fairly obvious here. We assume that <math>\sqrt{2}</math> is rational. From the definition of rational numbers, <math>\sqrt{2}</math> can then be written as a fraction in lowest terms. Let <math>\sqrt{2}=\frac{p}{q}</math>, where p and q are relatively prime. Squaring and multiplying by <math>q^2</math>, we have <math>2q^2=p^2</math>. As 2 divides the left hand side, it must also divide p (a very common example of divisibility being helpful). Let <math>p=2r</math>; then <math>2q^2=4r^2\rightarrowq^2=2r^2</math>. By the same argument as last time, we let <math>q=2s</math>. However, now we have <math>\sqrt{2}=\frac{p}{q}=\frac{2r}{2s}=\frac{r}{s}</math>. 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 <math>\sqrt{2}</math> must indeed be rational.
 +
 
 +
===Induction===
 +
 
 +
===Infinite Descent===
 +
 
 +
[[User:Temperal/The Problem Solver's Resource|Back to Introduction]]

Revision as of 19:07, 10 January 2009

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

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.

Induction

Infinite Descent

Back to Introduction

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=User:Temperal/The_Problem_Solver%27s_Resource_Proofs&oldid=29370"