>> Hi there. And welcome to this screencast where we're going to be starting to explore different ways of proof. We have looked at direct proofs of conditional statements in several places and in this section we're going to start introducing alternatives to direct proof, kind of one by one. So the first method we're going to look at is called proof by contraposition. And a proof by contraposition what we're going to do is we're still proving a conditional statement but we're going to prove the contrapositive of that statement instead. Now, let's review a little bit about what we know about the contrapositive. The contrapositive of a conditional statement, if P then Q, is the conditional statement if not Q then not P. So, to form of the contrapositive, remember we're going to switch the conclusion and the hypothesis of the original statement and negate each. And so contrapositive. And the main thing to know about the contrapositive other than how to form it is that it's a logically equivalent to this statement that we started with. So, if I wanted to prove a statement if P then Q and for whatever reason that was hard or unappetizing or whatever, I could form its contrapositive. And if I can prove it then it's equivalent to proving the original statement and possibly, in some cases the contrapositive will be easier to work with. So, let's look at an example of this using just simple notions of evenness and oddness. So, here is a conjecture, if N squared is even and N is an integer here, I should have said that. If N squared is even, then N is even. Now, in a direct proof of this statement, if I wanted to prove this directly. Okay, the first line would be to say, assume N squared is even. So I would assume that N squared is even. And a lot would take place perhaps in the proof, blah, blah, blah, blah, and at the very last line would say therefore N is even. Now just think about what would go in in the blah, blah, blah. What would go in the middle? I would start by assuming something about N squared being even and I want to conclude something about N being even. Now normally when you go from N squared to N it involves taking a square root of something. Now that seems a little weird, okay. And square to being even, I could say that there exists an integer K such that N squared equals 2K and then maybe the bright idea would be to take the square root of both sides. Okay. That isn't a big deal on this side but the square root 2 times K? I would like that to be another even integer. This seems like it would be pretty hard to even think that that's an integer at all much less an even integer. So, a direct proof of this is a little, sort of, unappealing because taking a square root which is the natural operation to get from the hypothesis to the conclusion doesn't seem to be working very well for us. So, this is an excellent opportunity to try to contrapositive instead. So here's what the contrapositive of the statement that we are trying to prove would look like. Okay, I would need to reverse the hypothesis and conclusion and negate each. So, it would say if N is not even and not even means odd, so if N is not even, or odd, then N squared is odd. So, that's what the contrapositive of the statement were trying to prove would say. And it's equivalent -- these two things are logically equivalent. So if I prove one, I've proven the other. And the reason the contrapositive would it be an appealing idea here is that if I assume that N is odd, it's pretty easy to get from N to N squared, okay. If N is odd that means there's an integer out there, K such as N equals 2K plus 1. And it's easier to conceptualize squaring both sides of this equation than it would be taking the square root of both sides of this equation. So, this seems like a good opportunity to use the contrapositive. So, let's go with it. I've got a blank slide over here and we're going to set up a no-show table. So, here's my column for the step. Here I will put the thing that I know at that step and over here I'll put the reason. This is actually a fairly short proof once we have this written down here. So. we're going to prove the contrapositive. So, the first thing we are going to assume is to assume that N is odd. N is odd. And that -- the reason is the hypothesis. The very last line of the proof is going to conclude that N squared is odd and we don't really know what the reason for that is yet. So, to get from here to here, let's start with a forward step with just saying there exists an integer, K, such that N is equal to 2K plus 1 and that's the definition of odd. Okay. Nothing surprising at this point. But now, let's think what we need to do. I know something about N and I want to conclude something about N squared. So let's square both sides. So this means that N squared is equal to 2K plus 1, the quantity squared. And that's just algebra, specifically it's squaring both sides of an equation. So let's use the FOIL method to expand out the right hand side. That would give me 4K squared plus 4K plus 1. Again, that's FOIL-ing, algebra, whatever you want to call it. Let's now factor out a 2 from some of these terms here. Two K squared, 2K, plus 1, again that's algebra. That's factoring. And then , this is a very familiar feeling proof at this point. I am going to take this thing and say that is an integer. So P5 is going to say that, let's say Q equals 2K squared plus 2K is actually an integer. I'm going to make that claim in the reason is because of the closure of these set of integers under multiplication and addition. And if so, therefore, what I have done here just to put one last line here. Is I have now I have written in squared is equal to 2Q plus 1 where Q is an integer. And again, I've done that by setting to equal to 2K square plus 2K. And then that gets me to the end. Now that I've written the end squared is equal to this form right here. I know N squared is odd so that's the definition of odd. So, this is a pretty basic proof, right, this is a proof that's quite like some of the ones you've seen before. How do we get there? Well, we have this statement that's what we've really proven is that if N squared is even, then N is even. Although it doesn't look like that. The word even never appears that's because we're proving the contrapositive instead. But since we've proven to the contrapositive and at the contrapositive is equivalent to this statement, we've actually proven the statement that we wanted. So, we are done. So proof by contrapositive. We're going to see another example in the next screen cast. So, thanks for watching.