>> Welcome back to our first look at mathematical induction. We left off the last video by explaining the method of mathematical induction. It's a two-stage process that's used when we're trying to prove that a predicate is true for all positive integers. The first step is to prove that the predicate is true for the case N equals one. The second step is to prove that if the predicate is true for an arbitrary positive integer K, then the predicate's true for K plus one. In other words, in the first step we proved that P of one is true using just a constructive proof, we simply plug one into the predicate, we get a statement, and we just need to see if that statement is true. The second step is a conditional statement that we have to establish, so we do that with a direct proof by assuming P of K is true and then proving P of K plus one is true. The first step here is often called the base case for the proof, because it's here that we "get on the stairwell," so to speak. The second step is called the inductive step, and P of K, the thing that we assume in that step, is called the inductive hypothesis. If we establish the base case and then prove the inductive step, then the predicate is true for all positive integers N. So, let's go back to the proposition we saw earlier and prove it by mathematical induction. Remember, the proposition says that for all positive integers N, the sum one plus two to the first plus two to the second all the way to two to the Nth is equal to two to the N plus first minus one. So, as before, let's let P of N be the predicate that's represented by this entire equation. And we put in a value of N for this left side and for the right-hand side, we'll get a statement that's either true or false, and so it's a predicate. We're trying to prove that the predicate is true for all positive integers N. So, by mathematical induction, we first need to establish the base case by proving that P of one is true. In other words, when I put in N equals one everywhere, I need to check to see if the resulting statement is true. This is an equation, so let's deal with each side separately. If I put in N equals one on the left, I get one plus two to the first power, which is equal to three. If I put N equals one on the right, I get two to the second power minus one, which is three. So, the two sides are equal, and that establishes that P of one is true, and so we've established the base case. We actually did this work earlier, we were just playing around with a problem, if you remember. So, now it's on to the inductive step. Remember here we're going to prove that if P of K is true for some positive integer K, then P of K plus one is true. This is an if-then statement, so we need to assume something and then prove something. For a concept check, what are we going to assume in the inductive step? Here are some choices. Pause the video and select the one you think is right. The answer here is E. You can immediately eliminate the first three options here because they are not even predicates. If you put in a value for K here, you do not get any kind of true or false logical statement but just an expression that doesn't have any truth value. What we're assuming in the inductive step is the truth of some statement, and so the answer has to be a statement, that leaves the last two. So, why is it E and not D? Well, you can tell by taking a look at what the predicate P of N actually says. What we were assuming is that if you replace N with K, then the statement is true. Well, if you replace N with K, you should have a K plus one here on the right-hand side, and that only happens in choice E, so E here is what we assume, it's what we called our inductive hypothesis. Now that we've identified what we were assuming in the inductive step, let's identify what we need to prove. For another concept check, what is that? What are we going to prove now? The answer this time is this time is D. We're going to prove that the statement P of K plus one is true. And again, if you just remember what P of N stands for in general, then it's easy to see that if you replace the N with a K plus one on the left, you're going to end the sum with two to the K plus one, and the right we're going to have two to the K plus one, plus one, and that's equal to two to the K plus two. So, now let's move on to the proof of the inductive step. Again, we're going to assume that for some positive integer K, the sum one plus two to the first, plus two to the second, plus two to the third, all the way up to two to the K, is equal to two to the K plus one, minus one. And we're going to prove that given this assumption, the sum one plus two to the first, plus two to the second, all the way up to two to the K plus one, is equal to two to the K plus two minus one. So, in other words, we're trying to prove an equation holds, and so the best way to look at that is to look at each side individually. Let's look at only the left-hand side of the equation that we want to establish. One thing we can do here to help us is reveal some of the terms that are hidden in the dots. For example, the next term in the sum here at the beginning would be two to the fourth. The next to last term would be two to the K. Let's rewrite that sum as such. Now, here's where I can use my inductive hypothesis. Look at the collection of terms all the way up to the next to last one. The inductive hypothesis says that I know something about those terms. I can collect those terms and rewrite them as two to the K plus one minus one. So let's do that. That entire left-hand I started with now collapses into two to the K minus one, plus two to the K plus one. Now, here I have two terms of two to the K plus one, so I can rewrite again as two times two to the K plus one minus one. That two is just two to the first power. So, I can use the laws of exponents from algebra to rewrite this at two to the first, times two to the K plus one, is two to the K plus two, and that has a one subtracted to it. Now, if you pull back and look at the whole scope here, I've shown that the sum one plus two, plus two to the second, up to two to the K plus one, is indeed equal to two to the K plus two minus one, and that's what I wanted to show. And that ends the proof, because I've established the base case and then proven the inductive step. In other words, I've gotten on the stairwell and I've shown that I can get from one step to the next no matter where I am. So in the next few videos, we're going to continue with examples of this hugely powerful method of proof in a variety of contexts, so keep watching.