>> Welcome to the screencast where we're going to reveal just exactly how the fairytale about the traveler in the gnome infested staircase relates to mathematics. We'll get to that in a minute, but let's recap the moral of the story first. The traveler was able to climb as high as he wanted on that stairwell as long as he could do two things. First of all he had to be able to get on the first step of the staircase and then, secondly, assuming he made it up to a particular step, he had to be able to show he could get to the next step. Now those two items are enough to get onto any step of the staircase because if he can get on the first step then because he knows how to get from any step to the next one, he can then go to the second step. But if he's made it to the second step he can get to the third step because, again, he knows how to get from any step to the next one. From there he can get to the fourth and the fifth and so on. In other words, there is no step that he cannot get to eventually. Now let's see what the story has to do with math by looking at a new proposition. The proposition says that for all positive integers n the sum of 1 plus 2 the first power plus 2 to the second plus 2 to the third and so on all the way up to 2 to the nth is equal to 2 to the n plus 1 minus 1. So in other words, if you take the sum of 1 plus a bunch of powers of 2 in sequence, you'd get the next power of 2 minus 1. Let's play with this problem for a bit to get a handle on it. Let's try the smallest possible value of n, which is 1 and check the left hand side and then check the right hand side and see if they're really equal to each other. Now on the left if I set n equal to 1, I get 1 plus 2 to the first, which is 3. On the right if I set n equal to 1, I get 2 to the 1 plus 1 minus 1. That's 2 squared minus 1, which is 4minus 1 and that's 3. So those two sides are equal. So the equation holds in that particular case. Now if we try another value of n say n equals 5, then on the left I get 1 plus 2 the first plus 2 to the second plus 2 to the third plus 2 to the fourth plus 2 to the fifth and that is if you raise the powers out that would be 1 plus 2 plus 4 plus 8 plus 16 plus 32 and that adds up to 63. On the right hand side of the equation if I set n equal to 5, I'd have 2 to the sixth power minus 1 that's equal to 64 minus 1, which is 63. So the equation holds again. So the proposition is true in at least 2 values of n, n equals 1 and n equals 5. Those examples, of course, don't constitute a proof but they do help us understand that the proposition at least seems true and maybe there's just the tiniest bit of information about how to prove that proposition in those examples as well. Before we get into a proof, let's point out one thing here. The equation we're trying to prove here is actually a predicate or an open sentence that is being quantified. So remember that a predicate or an open sentence is a sentence that is almost a statement except we would need information about a variable to determine whether it's true or false. Let p of n be the predicate 1 plus 2 to the first plus 2 to the second and so on up to 2 to the nth equals 2 to the n plus 1 minus 1. This is the statement we're trying to prove true for all positive integers. It's a predicate is the equation true? Well, it depends, it seems. We know that the predicate is true for n equals 1 because we did an example. So we'd say P of 1 is true. We also know that it's true for n equal to 5. So we'd say P of 5 is true. What the proposition is really saying is that this predicate p of n is true for all positive integers n. Or in other words, we have a predicate and we claim that the truth set for that predicate is the set of all positive integers. So we're now going to present a completely new line of proof argumentation for just such situations. These are situations where we have a predicate to prove and we want to prove that this predicate is true for all positive integers. The proof technique is called mathematical induction. The proof technique proceeds in 2 steps, and I want you to think about where you've maybe seen these steps before. So to begin with suppose that we want to prove that the predicate p of n is true for all positive integers n. Then to prove it we're going do 2 things. First of all, were going to prove that p of 1 is true. That's just an example. And then we're going to move on and prove that for an arbitrary positive integer k if p of k is true then p of k plus 1 is true. If we can do those two things, then p of n is true for all positive integers. So this is just the story of the magic staircase in math form. Remember in the story if the traveler could get onto the first step and then show how to get from one step to the next there was no limit to how high he can go. Likewise for us mathematical induction is saying that if we can show that the predicate we want to prove is true at this first step when n is equal to 1 and then prove that if I can make it up to a step labeled k then I can go to the next step labeled k plus 1, then there is no limit to the values of n for which p event is true. And that's another way of saying that p event is true for all positive integers n. So this is quite different from the previous methods of proof that we've seen. So we'll have to instantiate this method several times before it begins to sink in. In the next screencast, we're going to begin this in earnest by proving the proposition that we set forth in this screencast using mathematical induction. So stay tuned.