|
Post number 500!
I was really trying to figure out what I could contribute to TL with my 500th post. I don’t really write very well or have any cool hobbies. I’m just a meagre C- Zerg and I can’t code or do graphics at all.
But I study pure math and when you first start proving things it can be very very tough. I know it was for me! So I thought I’d just write a bit about how to prove things in general and maybe give a sense for what math is kind of about and hopefully entertain or help someone.
Here we go~
What is a proof?
A proof is just a series of true statements that lead from one true statement to another. This is not perfectly precise (it can be made so studying logic and such) but it is a good way to think about it to make sure you’re on the right track!
Example: Ok, this is kind of a silly example but it’s just to illustrate the idea.
Question: Suppose that it is raining. Prove that water is flowing down the street.
Proof:
It is raining. Therefore the rain water is on the ground.
But, we have gravity! Thus the rain water flows down the street.
PITFALL NUMBER 1!
Asking the question: “Can I do this?” Not a confidence that like “I don’t know if I can solve this problem”, but like am I “allowed” to do this as my next step. Never think “is this allowed” it doesn’t mean anything and just gets you into trouble.
This is something that people say all the time and it really just shows that they aren’t thinking about this whole math this in the right way (in my opinion).
What does that even mean? “Can I do this?” It’s like there are some moves you can do if you tap the buttons just right. Or some secret tricks that you just have to know to be able to solve the problem and its some big hidden mystery.
Instead of asking “Can I do this?” ask the following pair of questions:
1) “Is this a true statement?”
2) “Is this going to help me solve the problem?”
Often the answer to “Can I do this?” is “Yea, you can. But why do you want to?” So with our new pair of questions we would instead say, “Yea, this is true. But it doesn’t really look too useful right now.”
To go with pitfall number 1, I bring you tip number 1.
TIP NUMBER 1:
Know your definitions. Math relies heavily of precise definitions. If you don’t know what they are, you can’t do the problem. Often if you just write down what everything in the problem means, the solution will magically appear. Most of the proofs you will do in your first year or two of math will be simple consequences of the definitions.
So let’s do a simple math proof and look at its structure and how we never pull any tricks or rabbits out of hats and just make logical deductions at each step to move through a sequence of true statements towards out desired result.
This will be an example of our first proof type, the direct proof. In this proof technique we just keep it nice and simple logically. We start with some assumptions and deduce, deduce, deduce our way to the thing we want to prove.
This is called a parity argument generally. The parity of a number is just if it is even or odd.
Problem: The natural numbers are {1,2,3,4,...}. Prove that the sum of two odd numbers is even.
Proof:
First, what does it mean for a number to be odd? We know the odd numbers are these guys 1,3,5,7,9,11,... but how can we really define what they are?
A natural number is called odd if its remainder when divided by 2 is 1.
Similarly, a natural number is called even if its remainder when divided by 2 is 0.
Notice that it follows from this definition that we can write any odd number as an even number plus 1.
Let n, m be odd natural numbers.
So, we have n=2k+1 for some k, another natural number.
Ex. 5=2*2+1.
Similarly, m=2j+1 for some j, another natural number.
Great! This is how basically all parity arguments go.
Now we want to know about their sum:
n+m
=(2k+1) + (2j+1)
=2(k+j)+1+1
=2(k+j)+2
=2(k+j+1)
Therefore, 2 divides n+m! Which means that n+m is even.
There you have it, a lovely result that we all knew already! It is common to do a fair number of proofs like these in a first year intro to proofs course and they really are helpful. Notice how we didn’t do anything weird. We just wrote down what it meant for a number to be odd and poof!
Let’s look at another type of proof that many of you are likely familiar with. Induction!
Induction is great, you can prove some awesome things.
Here is the idea behind induction:
Suppose p(n) is some statement that depends on n.
For example, p(n)=Boxer could own n noobs with one hand. Then p(20)=Boxer could own 20 noobs with one hand.
This all makes sense and p(n) has a truth value, either true or false, for all values of n, a natural number.
We want to prove that p(n) is true for all values of n, what do we have to show?
Step 1:
The base case. Prove that p(1) is true.
Step2:
Fix n, a natural number.
Suppose that p(k) is true for all k<n. This assumption is known as the inductive hypothesis.
Prove that p(n) is true.
Once we do this we will have prove that p(n) is true for all values of n! To give an idea of why this works, just consider what we are doing. We know p(1) is true by step 1. So, p(2) must be true by step 2. So p(3) must be true, so p(4) must be true etcetc one by one all the way up.
PITFALL NUMBER 2!
A proof by induction doesn’t prove that Boxer could beat infinitely many noobs with one hand(though he could). It only proves that he could beat any finite number.
I actually saw a grad student in one of my courses make this mistake in class so watch out!
TIP NUMBER 2!
Strong induction vs. Weak induction.
Strong induction is what I have laid out. It is very common to give weak induction. The only difference is in the induction hypothesis. In weak induction we only assume that p(n-1) is true instead of for all k<n. Logically they are equivalent (ie. If you have one you can prove the other one). So really there is no reason to not use strong induction as it can be applied to more situations, even though often you won’t need the full assumption.
So my tip is, always use strong induction because you can!
Induction problem.
Question:
Prove that the sum of the first n natural numbers is equal to n(n+1)/2.
This is a classic problem with a cool math story to go with it. Gauss was an amazing mathematician and when he was a young boy (6 or so, he gets younger every time the story is told) his teacher didn’t want to teach the class and just decided to give them some make-work. She told them to add up the numbers from 1 to 100. Gauss took about 15 seconds and then case up to the teacher saying he was done. The teacher of course didn’t believe him and was frustrated to find out that he was correct ^^. Gauss figured out this formula with a very clever argument that I’ll go through after we prove it by induction.
Proof:
Let n=1.
Then the sum of the first 1 natural numbers is 1. Notice that this is equal to (1+1)/2=2/2=1. So we are done the base case.
Now, suppose that the sum of the first k natural numbers equals k(k+1)/2 for all k<n.
Then consider the following sum:
1+2+3+4+.....+(n-2)+(n-1)+n = (1+2+...+(n-2)+(n-1))+n
Notice the suggestive brackets? We know what 1+2+3+...+(n-2)+(n-1) is! Its (n-1)(n-1+1)/2=n(n-1)/2 by the inductive hypothesis!
So now we just need to look at:
n(n-1)/2+n
=(n^2-n+2n)/2
=(n^2+n)/2
=n(n+1)/2
And this is exactly what we wanted.
Therefore the sum of the first n natural numbers is n(n+1)/2 for any n.
Now for the more awesome Gauss’ proof when n=100. It works for any n, so try to generalize it for kicks!
Take two copies of your sum and write one above the other, with the second in reverse order!
1 + 2 + 3 +...........+ 98 +99 + 100
100 + 99 + 98 +..........+ 3 + 2 + 1
Now we add them up in columns to get:
1+100 + 2+99 + .....+99+2 + 100+1
=101+101+.....+101+101
We get 100 copies of 101!
This is easy to calculate, 100*101=10100
But we have to divide by two because we took the sum twice:
10100/2=5050
Notice that we used 100*101/2, which is exactly n(n+1)/2.
Good old Gauss.
Proof type number 3! Proof by contradiction. These proofs are pretty slick.
The idea is that any statement is either true of false. So if we prove that it can’t be false, then it must be true! The problem with these proofs is that they are often not very helpful in terms of understanding what exactly is going on.
We’re going to do one of my favourites, a sexy little proof ^^.
First, the integers are these numbers: (...-2, -1, 0, 1, 2, .....}
The rational numbers are all the fractions (a/b where a and b are integers and b is not 0).
The irrational numbers are harder to define but suffice it to say that they are all the number that are not rational numbers. Basically, you can’t write it as a ratio of two integers. Actually..thats a pretty good definition.
Question:
Prove that the square roof of 2 (sqrt(2)) is not a rational number.
Proof: by contraction.
Suppose that sqrt(2) was a rational number.
Then sqrt(2)=a/b for some integers a, and b, where b is not 0 and it is in lowest terms. So like 2/4 is not in lowest terms because we could make it 1/2. So we can assume that a and b have no common factors because if they did we would just cancel them and get an equivalent fraction. This is key!
Square both sides to get:
2=(a/b)^2=a^2/b^2
By multiplying both sides by b^2 we get:
2*b^2=a^2
So, 2 divides a^2 as we wrote a^2 as 2 times something. So a^2 is even.
This implies that a itself is even! (this requires a proof, but it is a simple parity argument like above, try it!).
Now we can write a=2*k for some k, another integer.
So:
2*b^2=(2*k)^2=4*k^2
Dividing by 2 on both sides yields:
b^2=2*k^2
So 2 divides b^2 and thus 2 divides b.
This, 2 divides a, and 2 divides b. So a and b have a common factor of 2. But this is impossible as a/b was in lowest terms and thus had no common factor!
So we have found a contradiction. Therefore our original assumption must be false.
Our original assumption was that sqrt(2) was rational. So this cannot be the case. Therefore sqrt(2) must be irrational.
Mmmmm satisfyin~.
I’d like to wrap up with some good “tricks of the trade”.
Number 1:
Write down what everything is in terms of its precise definitions in explicit detail. This is always a good learning experience and will often lead immediately to the solution!
Number 2:
Do nothing in a clever way. This is quite common when you want to change the way something looks without changing what it is. So you multiply by 1 but you write the 1 as 15/15 and it makes things work out nicely. Another common trick is to add 0 but you 0 might look like 243-243 and then when you group things up in the right way it all falls out (completing the square is a good example of using this trick).
Number 3:
Do the only think you can. This is often how basic proofs in abstract algebra go. You just do the thing only that makes sense and follow your nose to the answer hehe.
Number 4:
Makes sure you used all of the hypotheses. If you get to the end of the proof and you didn’t use one of your assumptions then chances are good that you made a mistake. Profs almost never give extra assumptions.
Number 5:
Wishful thinking. This is an awesome one, but a bit more “advanced”. Essentially you say to yourself, “Wouldn’t it be nice if such and such? If I had such and such I would be done!” Then you try to prove that you really do have such and such! It works really nicely if you know what to look for and I recently used this to prove a problem on one of my algebraic topology assignments ^^.
Math is a lot of fun, and it’s something that most people never get to see in its true light. My school has a general first year so I didn’t really see what math was all about until second year though I got a taste in first. I am now in my fourth and last year of pure math and will be applying to grad school soon.
Hopefully someone found this interesting and maybe even helpful.
To anyone writing the Putnam on Saturday, best of luck!
<3 to all of you TL!
|
wow great write up i read all of it and understood it all
+ Show Spoiler +NOT
but good effort
maths suxz0r
i stopped at calculus in highschool
|
Okay if you're gonna do a write-up like this, you need to figure out who your audience is; a ton of TL'ers are fantastic at math, but you're not wirting to them are you? You're doing a write-up for novice magi---mathematicians. So, let me point something out.
Let n, m be odd natural numbers.
Then, n=2k+1 for some k, another natural number.
This is because n is odd. n being odd means that when you divide by 2, you get 1.
Ex. 5=2x2+1.
This makes zero sense. The third line does not refer to the first two in a sensical fashion. Please try to explain this better... I would -love- to understand this article but I stumble over this first proof because you took a ninety degree turn where you should have simplified. Take it slow for us noobies!
Other than that, I'm excited to work my way through this article.
EDIT: Now that I understand what you're saying, let me explain how you could rephrase it; very simple, when you say 'You get 1', the common man understands this as equalling 1, as in n/2=1 which obviously isn't applicable here. Also, you might preface this article with a definition of your operators, e.g.- Let - assumptions made at the beginning of the proof. Then - the computational output of the last input.
This way, it would be claer that you had your axioms after the Let phrase, and then isn't just a transitory word, it's an operator that says, N=2k+1. This is true because n is odd. It makes more sense that way, at least to me.
|
Fair enough, I made this change:
Let n, m be odd natural numbers.
So what does it mean for a number to be odd? We know the odd numbers are these guys 1,3,5,7,9,11,... Notice that all of them are some even number plus 1. We can always write an odd number as an even number plus 1.
So, we have n=2k+1 for some k, another natural number.
|
OH FUCK I forgot about the putnam again fml.
|
i'm not going to pretend to understand all of this stuff.. but its nice to get the inside scoop on whats really involved in a field im not a part of
congrats on your 500th post 
|
I don't know shit about math, but your first problem "prove that the sum of two odd numbers is even" doesn't make sense to me. What confuses me is that your proof seems to rely upon the statement "n being odd means that when you divide by 2, you get 1" which is in turn not proven. It seems apparent to me that that claim is true, when i do a few examples in my head (how else is it supposed to be apparent?), but that you didn't just give a few examples in that same way to prove the initial problem seems to suggest that that doesn't count as proof, or isn't good enough. It seems inconsistent to me i guess. Where did i go wrong?
|
On December 02 2009 12:12 zobz wrote:
I don't know shit about math, but your first problem "prove that the sum of two odd numbers is even" doesn't make sense to me. What confuses me is that your proof seems to rely upon the statement "n being odd means that when you divide by 2, you get 1" which is in turn not proven. It seems apparent to me that that claim is true, when i do a few examples in my head (how else is it supposed to be apparent?), but that you didn't just give a few examples in that same way to prove the initial problem seems to suggest that that doesn't count as proof, or isn't good enough. It seems inconsistent to me i guess. Where did i go wrong?
his proof is right, he just wrote it wrong. When you divide an odd number by 2 you get a REMAINDER of one is what he meant to say. This is equivalent to saying that the odd numbers are all the ones between the even ones. Which is the same as saying n = odd => n=2k+1 (for some integer k). This fact actually comes from the definition of odd which is just common knowledge in math.
|
Your question is awesome and I have edited the OP. Here is the explaination.
I have fallen into PITFALL NUMBER 1!!!
Know your definitions.
You are right, I didn't prove the statement "n being odd means that when you divide by 2, you get 1". But really, that is that being odd means. This is the definition of a number being odd.
Thank you
When I think of dividing in the natural numbers I think of it like long division back in elemntary school with remainders and such. I forget that not everyone does and so I'm glad you caught me on it ^^.
|
This is very cute, especially the sqrt(2) proof, which I hadn't seen before. Thank you for your contribution!
|
This is good shit i read the 2 proofs so far going to bed now tho. good read
|
good stuff, although not really new to me. one question though: i have always had troubles with continuity and convergence proofs using the epsilon-delta notation. do u maybe have any specific tips for these? id be very thankful 
|
nice article, what is really beautifill about this is that the method of thinking is aplicable to all things.
I think you could go into a little more of details about what a postulate (not sure about the exact term) is: basically the first "true" or supposely true statement in your chain of deduction
|
A proof by induction doesn’t prove that Boxer could beat infinitely many noobs with one hand(though he could). It only proves that he could beat any finite number.
When does that ever make a difference?
|
On December 02 2009 15:29 meaculpa wrote: Show nested quote +
A proof by induction doesn’t prove that Boxer could beat infinitely many noobs with one hand(though he could). It only proves that he could beat any finite number.
When does that ever make a difference?
Consider this:
The set of the first n natural numbers has a finite number of elements in it.
This is obviously true, but lets prove it by induction.
If n=1 then clearly {1} has only finitely many elements.
Now assume that {1,2,3,...,n} has finitely many elements, then {1,2,3...,n,n+1} has finitely many elements because adding one more elements cannot take is from finite to infinite.
So the set of the first n natural numbers has finitely many elements in it for any natural number n.
But, the statement, the set of the first infinity natural numbers (this is all of them) is finite is false.
Its a bit of a trivial example but it shows the point.
On December 02 2009 14:42 Black Gun wrote:good stuff, although not really new to me. one question though: i have always had troubles with continuity and convergence proofs using the epsilon-delta notation. do u maybe have any specific tips for these? id be very thankful
So there are a few things about these types of proofs that I have learned. The first is how important it is to copy down the definitions. I always start these proofs by writing down the definition of continuity or convergence because you use it so directly in these proofs. Even after doing so many of them I still find it super helpful.
The next thing is that the final proof doesn't come through on the first try.
In the final proof you'll fix epsilon>0 then make a super clever choice of delta. Maybe something like epsilon^3/(4+epsilon) or something like that. But, this doesn't really come through the first time.
Your main tool is almost always the triangle inequality. This is how you get from the thing that you want to get small to the things that you know gets small (if that makes sense). In my first real analysis course I remember the upper year students telling me that the course is basically an exercise in the triangle inequality heh.
So let’s do an example, and hopefully it will make some of this clear.
I’m going to use e for epsilon, and d for delta.
Question:
Lets prove that the sum of two continuous functions from the real numbers to the real numbers is again continuous.
Prep work:
Let f and g be continuous functions from R to R.
Then f and g are continuous at each point in R.
Fix e>0, and c a real number then there exists d1>0 such that
|f(x)-f(c)|<e for |x-c|<d1
and d2>0 such that
|g(x)-g(c)|<e for |x-c|<d2
Great. We have written down the definitions precisely!
Now we want to check out |(f+g)(x)-(f+g)(c)| and show that is gets less than epsilon.
|( f+g)(x)-(f+g)(c)|=|f(x)+g(x)-f(c)-g(c)|=|f(x)-f(c)+g(x)-g(c)|
Now we use the triangle inequality:
|f(x)-f(c)+g(x)-g(c)|<=|f(x)-f(c)|+|g(x)-g(c)|
And now we’re golden because we know all about those two things from the continuity of f and g.
First let d=min(d1,d2). Then we get:
|f(x)-f(c)|+|g(x)-g(c)|<= e+e=2e for |x-c|<d
Awesome. So we’re pretty well done.
We have shown that |(f+g)(x)-(f+g)(c)|<2e. This is pretty much all we need, but really we want it to be less than that e we fixed.
So now we look at our proof and realise that in order for |f(x)-f(c)|+|g(x)-g(c)|<e, we need each of those two pieces to be less than e/2 and we’ll be set!
So now when we go to write up the proof good, we’ll know to choose d1 and d2 so small that
|f(x)-f(c)|<e/2 and |g(x)-g(c)|<e/2.
Let's do it.
Proof:
Fix e>0 and let c a real number be arbitrary.
Then, there exists d1 and d2 such that:
|f(x)-f(c)|<e/2 when |x-c|<d1
|g(x)-g(c)|<e/2 when |x-c|<d2
By the continuity of f and g.
Define d=min{d1,d2}.
|(f+g)(x)-(f+g)(c)|=|f(x)-f(c)+g(x)-g(c)|<=|f(x)-f(c)|+|g(x)-g(c)|<=e/2+e/2=e when |x-c|<d.
So f+g is continuous at c. But c was arbitrary, so f+g is continuous on all of R.
So to sum up.
Write down what you know.
Use the triangle inequality to show that the thing you want to prove is less than epsilon is less than a sum of things that you know get very small (often less than e/2 or e/3, something like that)
And you’re done!
I think an important part is the prep work. Don’t worry about it coming out perfectly. Just show that the thing you want to get small gets smaller than something times epsilon. Then you can adjust your earlier choices and make the proof look pretty as we did here by taking e/2 instead of e.
Often these types of problems involve adding 0 in a clever way so that we can introduce something that we know about. And then using the triangle inequality.
I don’t know if this is what you were looking for so let me know if I can help in any other way. If you have a specific problem please ask and I’d be happy to assist.
These replies and up so long >>
|
hAHhaha awesome entry!
I'd read it but I have to do algebraic geometry 
but it's always nice to see fellow math people around!
|
Ah, ya I'm working on algebraic geometry myself!
This stuff is crazy xD
|
Ah nice, you could use something like this to make it easier to read though: http://www.texify.com/links.php
I liked my Analysis course last year, where everything was proved from: "Every non-empty bounded subset of real numbers has a least upper bound."
|
On December 03 2009 08:49 Nytefish wrote:
I liked my Analysis course last year, where everything was proved from: "Every non-empty bounded subset of real numbers has a least upper bound."
I think you mean "has a least upper bound that is a real number."
The way you worded it is ambiguous I think; non-empty sets in Q always have a least upper bound as well, but the LUB may not be a rational. It's not clear to me that saying the LUB of a set of rationals may not be rational is the same as saying it does not have a least upper bound.
|
On December 03 2009 11:33 crate wrote:Show nested quote +On December 03 2009 08:49 Nytefish wrote:
I liked my Analysis course last year, where everything was proved from: "Every non-empty bounded subset of real numbers has a least upper bound." I think you mean "has a least upper bound that is a real number." The way you worded it is ambiguous I think; non-empty sets in Q always have a least upper bound as well, but the LUB may not be a rational. It's not clear to me that saying the LUB of a set of rationals may not be rational is the same as saying it does not have a least upper bound.
It may be a bit ambiguous, but I haven't even defined exactly what I mean by least upper bound, or any other of the terms in that statement. That statement doesn't imply anything like rational sets having a rational LUB but I might be misunderstanding you.
|
This was cool, thanks!
I always had no idea what to do, as I never really learned proofs. "Prove that x = y" My first thought was always "wtf does that mean, I can't PROVE it, it just will" and then I'd move terms around or whatever until x = y. (This is first year general math stuff).
Only problem i have with this (in general) is the law of excluded middles, which I'm not really a fan of.
http://en.wikipedia.org/wiki/Intuitionism
|
|
|
|
|
|
EPT
