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"

(→‎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: 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: 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===
 +
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 19: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 $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

Induction is used when we need to prove a statement true for an infinite sequence of numbers $S$; 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 $1$. Then we take an inductive step; proving that if $k$ satisfies the statement, then $f(k)$ does as well, where $f:S\rightarrow S$ is a function that takes one member of the sequence to the next. In the case of the natural numbers, it's $k+1$. Now, since the statement is true for $1$ (in the case of the natural numbers), it's true for $1+1$, as well, and $1+1+1$, 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 $k\in S$ so that $k<f(k)$ satisfy the statement to prove that $f(k)$ satisfies the statement. In terms of the natural numbers, this means we have to use the fact that $1,2,3,\ldots,k$ satisfy the statement to prove that $k+1$ does.

Example Problem 3

The function $f(x,y)$ satisfies

(1) $f(0,y)=y+1,$

(2) $f(x+1,0)=f(x,1),$

(3) $f(x+1,y+1)=f(x,f(x+1,y)),$

for all non-negative integers $x,y$. Show that $f(1,y) = y+2$ for all non-negative integers $y$. (Adapted from 1981 IMO, #6)

Solution

We observe that $f(1,0) = f(0,1) = 2$ and that $f(1, y+1) = f(1, f(1,y)) = f(1,y) + 1$, hence by induction, $f(1,y) = y+2$, as desired.

Example Problem 4

Let $1 \le r \le n$ and consider all subsets of $r$ elements of the set $\{ 1, 2, \ldots , n \}$. Each of these subsets has a smallest member. Let $F(n,r)$ denote the arithmetic mean of these smallest numbers; prove that

$F(n,r) = \frac{n+1}{r+1}.$

(1981 IMO, #2)

Solution

We proceed by strong induction.

We define $F(k, k-1)$ to be zero (the empty sum).

We consider $r$ to be fixed. The assertion obviously holds for $r = n$. We now assume the problem to hold for values of $n$ less than or equal to $k$. By considering subsets containing $k+1$ and not containing $k+1$, respectively, we conclude that

$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}$.

as desired.

Infinite Descent

Back to Introduction

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