Proofs. Let's talk about proofs. There's a big mystique about proofs. Proofs are apparently extremely hard, but a proof is just a bit of precise reasoning. And proofs are hard and only, in so far, as it is hard to be precise. Now, there are many kinds of proofs and I can't enumerate all of them but I can just give a few types. The simplest proofs are just transformations. You start with an expression, you do things to that expression that are allowed and you get a new expression which hopefully tells you a little bit more about the things you want to know. The second principle, very important one, is induction and it underlies the definition of the natural numbers. The third principle is proof by contradiction. It is a favorite among mathematicians and it works very neatly when it works. The fourth is a rather low by the ground technique to proof by exhaustion of possibilities. And the fifth kind of proof, which sometimes can be a little bit abstract, is an existence proof when the thing that is shown to exist isn't determined precisely. So we'll give all these five types, we'll give examples. So let's start with a proof by transformation. And what I'm going to show is how you derive the solution equation to the general quadratic polynomial. So you've got an equation like this: X is the unknown. They want to solve x in terms of a, b, and c. How do you do that? Well, the first thing you do is you divide out A if that is permitted, so that's X-squared plus B over A X plus C over A is zero. Or the other possibility, A is zero. The second step of the prove is a bit technical and it's called completing the square. You write X-squared plus two times B over two A times X and then you add a term which would make the first three terms a perfect square, which is in this case, B-squared over four A-squared. Having added that term, you subtract it again and you add it C over A which is zero. Now, the first three term are perfect three terms are perfect square which we express by writing it as X plus B over two A-squared. And if we multiply that out, we get exactly X-squared plus two times B over two A times X plus B over two A-squared. And there's another term, which we will bring to the other side, which is B-squared over four A-squared minus four A times C over four A-squared, so that we can actually bring it under the same denominator later. Now we can take left and right square roots and we get X plus B over two A is either the square root of B-squared minus 4 A_C divided by 4 A-squared; or X plus B over two A is minus that same square root. And then we get the final form, X is minus B over two A plus, we can take four over A-squared out of the square root and get two A the square root of B-squared minus 4 A_C; or X is minus B over two A minus one over two A the square root of B-squared minus 4 A_C. Of course, we can do all this only if A is not equal to zero. But we can deal with that case. Then, A-squared X plus B_X plus C is zero is actually a linear equation. So that's not really the equation we wanted to solve. Now, this is the famous solution formula of the quadratic equation and we obtained it just by a number of steps. Nothing more, nothing less. And there was only one step where we had to take care was the second step where we divided out A and if we divide out a number, the number shouldn't be zero. That is a proof for transformation. The second proof technique is a proof by induction. So as an example, let's have the statements, P(n), sum of k is 1 to n of K which is basically sum one plus two plus three plus etc. plus K is equal to N plus one over two and well, we can first ask our-self whether P zero is true. The sum of k is 1-2-0 of K is by definition a zero. This definition always holds if the index starting value of the index is higher than the ending value. So on the other hand, n plus one divided by two, if we take n as zero, is also equal to zero. So we see that P zero is true. The second thing we have to show that if p_n, then also p_n plus one is true. This is a little calculation. If we start by p_n, that is basically the same thing as saying that the sum of k is one to n, of k is equal to n, n plus one over two. This implies if we add n plus one left and right. That, well, on the left hand side, you see, this is just the sum of k is one two n plus one of k. And on the right hand side, we see by taking n plus one out of the brackets and over two plus one that this is nothing else than n plus one times n plus two divided by two which is the same thing as n plus one, n plus two divided by two. So this is just p_n plus one. So we've shown two things. First, we've shown that the first statement, P zero is true. This is called the initialization of the induction. And then we've shown that if p_n is true then also p_n plus one is true and that for every n, which this is called the induction step which basically means, well first, we have P zero. If P zero is true, then P one must be true. If P one must be true, then P two must be true. So, the conclusion is that P_n is true for every n in the natural numbers. This is the principle of proved by mathematical induction. The third principle is prove by contradiction. And it is proved to show the following famous theorem which goes all the way back to Euclid. There are infinitely many prime numbers. Remember, prime numbers and natural number not equal to one which can only be divided by itself and by one. So how does the prove go? The prove goes by supposing that the theorem is false. Suppose this is not the case. Then there are only finitely many prime numbers so we can call prime numbers P one, P two, until P capital N. And those are all the prime numbers. Now we're going to consider the following number q which is P one times P two times P three times, I'm just multiplying all my prime numbers, definitely many, P_N get a very big number but that is of no importance and I add one to it. Now, q is not divisible by P one because if I would divide q by P one, I get a remainder of one. Nor is it divisible by P two because if I would divide it by P two, I get the remainder of one, etc. nor by any of the primes. Well, Q is the number which cannot divided by any prime number. It can also not divided by any number that is a product of prime numbers because then it should be divisible by the prime numbers themselves. So that means that q is prime. But clearly q is bigger than P_N. So P_N is not the biggest prime. So our assumption that we had finitely many prime numbers, yielded a new prime number. So we assume that our capital N prime numbers and now we found another one, so the capital N plus one, but that's, of course, a contradiction because the number of prime numbers cannot be N and N plus one. So we get a contradiction. I always mark these with a little flash and since the assumption we made that the theorem is false led into a contradiction, the theorem must be true. Our fourth proof technique is the one by exhaustion of possibilities and to illustrate that we look at the theorem that the square root of two is not a rational number so it is also, by the way, proof of contradiction. We start by assuming that square root of two is a rational number. P over Q. We may assume that P and Q do not have a common factor. For if they had a common factor, we can divide it out. Okay. So P and Q do not have a common factor. So there are two possibilities. The first possibility is that P is odd and the second possibility is that P is even and Q is odd. And in the first case when P is odd, Q might be either odd or even. Now, let's first have a look at the possibility that P is odd. As we assume that P over Q is equal to the square root of two and follow set P-squared over Q-squared is equal to two and it follows that P-squared is two times Q-squared. But we know, we also know that P is odd and the square of an odd number, of an odd integer, is again odd. And there is a contradiction because in the first line we show that P-squared is even and in the second line we show the P squared is odd. So that cannot be the case. P cannot be odd. So let's look at a second possibility. P is even and Q is odd. Well, Q is necessarily odd because otherwise P and Q would have effect in common and that we excluded. So we have that P is two to the power K times R with K larger equal than one and R an odd number. We also have again, as above, that P-squared will be two times Q-squared. That will imply that two to the power two K times R-squared is equal two times Q-squared. Now, as K is larger equal than one, two to the power two K is four or eight, at least that has a factor four. So we can write this as two to the of power two K minus one times R-squared is Q-squared and two k minus one is larger equal than one. So from this it would follow that Q is even and again we've reached a contradiction. So if we've exhausted all the possibilities and we found there is no P over Q such that P-squared over Q-squared can be equal to two. So we showed that the square root of 2 isn't and cannot be a rational number. As a final proof let's have a look at an existence proof. And the existence proof I'm going to show you is rather simple. Assume there are 100 drawers and 101 socks. Assume moreover that each sock lies in one of the 100 drawers. Then there is one drawer with at least two socks in it. Of course, this all looks rather whimsical but if you think about it, you know exactly that there must be a drawer where there are two socks in it, at least one drawer and there must be at least two socks in one of the drawers. But you can't tell a priority which of the hundred drawers it is. You only know that it must be there and the only way to find it is to open each and every one of them. Now this is typical for what happens with an existence proof. You know that a certain object exists, in this case, a drawer with at least two socks, but you don't know where to find it. So that makes existence proves a little bit tricky to imagine but having the existence of something is often very useful and in case you are an economist, you will be doing this all the time when dealing with general equilibrium theory where you can prove that an equilibrium, a general equilibrium exists but you've got no idea where to find it.
