Difference between revisions of "User:Temperal/The Problem Solver's Resource Proofs"
(→Contradiction) |
(→Example Problem 3: from the wiki) |
||
(5 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Methods of Proof== | + | __NOTOC__ |
− | 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. | + | {{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. | ||
− | ==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 | + | ====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. | ||
− | Example 2 | + | ====Example Problem 2==== |
+ | Prove that <math>\sqrt{2}</math> is irrational. (Also a very classic question) | ||
− | Solution | + | =====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=== | ||
+ | Induction is used when we need to prove a statement true for an infinite sequence of numbers <math>S</math>; commonly the natural or whole numbers. The procedure is as follows: Show the desired statement true for a '''base case''', the smallest number in the sequence - in the case of the natural numbers, it would be <math>1</math>. Then we take an '''inductive step'''; proving that if <math>k</math> satisfies the statement, then <math>f(k)</math> does as well, where <math>f:S\rightarrow S</math> is a function that takes one member of the sequence to the next. In the case of the natural numbers, it's <math>k+1</math>. Now, since the statement is true for <math>1</math> (in the case of the natural numbers), it's true for <math>1+1</math>, as well, and <math>1+1+1</math>, etc. Thus, it's true for every natural number. A common analogy is a row of falling dominoes. | ||
+ | |||
+ | '''Strong induction''' is a method where we have to use the fact that all <math>k\in S</math> so that <math>k<f(k)</math> satisfy the statement to prove that <math>f(k)</math> satisfies the statement. In terms of the natural numbers, this means we have to use the fact that <math>1,2,3,\ldots,k</math> satisfy the statement to prove that <math>k+1</math> does. | ||
+ | |||
+ | ====Example Problem 3==== | ||
+ | The function <math>f(x,y)</math> satisfies | ||
+ | |||
+ | (1) <math>f(0,y)=y+1, </math> | ||
+ | |||
+ | (2) <math>f(x+1,0)=f(x,1), </math> | ||
+ | |||
+ | (3) <math>f(x+1,y+1)=f(x,f(x+1,y)), </math> | ||
+ | |||
+ | for all non-negative integers <math>x,y </math>. Show that <math>f(1,y) = y+2 </math> for all non-negative integers <math>y</math>. (Adapted from 1981 IMO, #6) | ||
+ | |||
+ | =====Solution===== | ||
+ | We observe that <math>f(1,0) = f(0,1) = 2 </math> and that <math>f(1, y+1) = f(1, f(1,y)) = f(1,y) + 1</math>, hence by induction, <math>f(1,y) = y+2 </math>, as desired. | ||
+ | |||
+ | ====Example Problem 4==== | ||
+ | Let <math>1 \le r \le n </math> and consider all subsets of <math>r </math> elements of the set <math> \{ 1, 2, \ldots , n \} </math>. Each of these subsets has a smallest member. Let <math>F(n,r) </math> denote the arithmetic mean of these smallest numbers; prove that | ||
+ | |||
+ | <center> | ||
+ | <math> | ||
+ | F(n,r) = \frac{n+1}{r+1}. | ||
+ | </math> | ||
+ | </center> (1981 IMO, #2) | ||
+ | |||
+ | =====Solution===== | ||
+ | We proceed by strong induction. | ||
+ | |||
+ | We define <math>F(k, k-1)</math> to be zero (the empty sum). | ||
+ | |||
+ | We consider <math>r</math> to be fixed. The assertion obviously holds for <math>r = n</math>. We now assume the problem to hold for values of <math>n</math> less than or equal to <math>k</math>. By considering subsets containing <math>k+1</math> and not containing <math>k+1</math>, respectively, we conclude that | ||
+ | |||
+ | <center> | ||
+ | <math> | ||
+ | F(k+1, r) = \frac{{k \choose r-1}F(k,r-1) + {k \choose r}F(k,r)}{{k+1 \choose r}} = 1 + \frac{k-r+1}{r+1} = \frac{k+2}{r+1} | ||
+ | </math>. | ||
+ | </center> | ||
+ | |||
+ | as desired. | ||
+ | |||
+ | ===Infinite Descent=== | ||
+ | |||
+ | [[User:Temperal/The Problem Solver's Resource|Back to Introduction]] |
Latest revision as of 20:26, 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
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.
Example Problem 2
Prove that is irrational. (Also a very classic question)
Solution
The assumption should be fairly obvious here. We assume that is rational. From the definition of rational numbers,
can then be written as a fraction in lowest terms. Let
, where p and q are relatively prime. Squaring and multiplying by
, we have
. As 2 divides the left hand side, it must also divide p (a very common example of divisibility being helpful). Let
; then $2q^2=4r^2\rightarrowq^2=2r^2$ (Error compiling LaTeX. Unknown error_msg). By the same argument as last time, we let
. However, now we have
. 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
must indeed be rational.
Induction
Induction is used when we need to prove a statement true for an infinite sequence of numbers ; commonly the natural or whole numbers. The procedure is as follows: Show the desired statement true for a base case, the smallest number in the sequence - in the case of the natural numbers, it would be
. Then we take an inductive step; proving that if
satisfies the statement, then
does as well, where
is a function that takes one member of the sequence to the next. In the case of the natural numbers, it's
. Now, since the statement is true for
(in the case of the natural numbers), it's true for
, as well, and
, etc. Thus, it's true for every natural number. A common analogy is a row of falling dominoes.
Strong induction is a method where we have to use the fact that all so that
satisfy the statement to prove that
satisfies the statement. In terms of the natural numbers, this means we have to use the fact that
satisfy the statement to prove that
does.
Example Problem 3
The function satisfies
(1)
(2)
(3)
for all non-negative integers . Show that
for all non-negative integers
. (Adapted from 1981 IMO, #6)
Solution
We observe that and that
, hence by induction,
, as desired.
Example Problem 4
Let and consider all subsets of
elements of the set
. Each of these subsets has a smallest member. Let
denote the arithmetic mean of these smallest numbers; prove that
(1981 IMO, #2)
Solution
We proceed by strong induction.
We define to be zero (the empty sum).
We consider to be fixed. The assertion obviously holds for
. We now assume the problem to hold for values of
less than or equal to
. By considering subsets containing
and not containing
, respectively, we conclude that
.
as desired.