EPTI 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!
