>> Welcome back to another screencast on induction. In this video we're going to look at yet another variation on the theme of induction that works in serving cases where our current notion of induction doesn't work. Let's motivate this with an example. We're going to prove a basic fact in arithmetic that every integer greater than one can be factored into a product or prime numbers. By product, we mean that either the integer itself is a prime number, so it's like a product with just one term in it, or it's a bunch of primes multiplied together. So you might have thought this was an axiom of arithmetic, you know, something that we just accept without proof. But actually, we can provide a proof for this that uses kind of a structural approach. We're going to use induction to prove this mainly because in this result we can see that the problem can be solved using simpler, smaller versions of itself. To see this, think about how you would factor an integer like 144. You might first notice that 144 is even, so you could factor it into two times 72. Now what you do is continue factoring the results. Seventy-two splits into two times 36, 36 is six times six. The six on the left is two times three, and the six on the right is also two times three. So we reached a stopping point now where all the endpoints of this little tree structure here are primes. Then we can begin to build up the answers. So 144's factorization is two to the fourth times three to the second. Because we're repeating the same operation of factoring off small numbers on repeatedly smaller versions of the problem, that makes this think that induction, which is a proof technique based on exactly that, working with simpler versions of a problem to prove a large version, is well suited. In fact, this factoring method is what we call a recursive algorithm, a process that calls simpler versions of itself. And we're going to be looking into that in the next section. So let's try to set up a proof by induction here for our proposition. Induction involves identifying a predicate that's being claimed as true and then identifying the range of natural numbers for which we think the predicate is true. In the principle of mathematical induction, the predicate is a function of N and is claimed to be true for all natural numbers. In the extended principle of induction, which we learned about in an earlier video, we have a predicate that's claimed to be true for values of N that are greater than or equal to a certain threshold. So the first thing we need to do is identify the predicate. If you rewrite the proposition slightly, it becomes clear. Rewrite it to say for every natural number N greater than or equal to two, N can be written as a product of prime numbers. That's the same thing as the original proposition but just slightly rewritten. And it's easy to pick off the predicate here. P of N, which we'll call the predicate, is the statement N can be written as a product of prime numbers. And we're claiming here that P of N is true for all N greater than or equal to two. So let's start a proof by induction, and we're going to see there's a bit of a problem in the inductive step. First, let's start the base case with N equals two. Well P of two is true because two itself is a prime number, and remember that we said a product, quote/unquote, can be just a single prime by itself. So the base case is established. Now on to the inductive step. We're going to assume that P of K is true for some K greater than or equal to two. And we want to prove that P of K plus one is true. That is, we're going to assume that the integer K can be written as a product of primes, and then we're going to try to prove that K plus one can be written as a product of primes. But here's where we run into a problem, namely, it's not really easy to see how the inductive hypothesis can be used here. I know that if K can be factored into a bunch of primes, it may not help me to see that K plus one can be factored into primes. For example, suppose you knew what the prime factorization of the number 2,000 was. Does this help you factor 2,001? Not really. There's no natural relationship between the factorization of 2,000 and the factorization of 2,001. So we're not going to get a lot of traction out of our induction hypothesis here. So what we'll do instead is introduce another version of induction that can be helpful. The truth of P of K might not be helpful to prove P of K plus one but the fact that the predicate is true for some value of the variable would be. For example, knowing the prime factorization of 2,000 doesn't help you much in finding the factorization of 2,001. But knowing the factorization of 667 does. Why is that? Well 2,001 is equal to three times 667. So you can just happen to know the factorization of 667, and you can go find that that's equal to 23 times 29. It wouldn't be hard at all to come up with the factorization of 2,001, because you could just split off the three and then use 667's factorization to complete the whole thing. In other words, knowing P of K might not help you prove P of K plus one, but knowing P of one or more values of the variables less than or equal to K might. So this is called the second principle of mathematical induction, and it goes like this. Suppose M is an integer and we're trying to prove that a predicate P of N is true for all N greater than or equal to M. This is the same setup as the extended principle of mathematical induction. Then the second principle says that we first prove P of M is true as a base case. Then we assume that P is true for all the integers between M, the base case, and some integer K. So again, we're assuming not only that P of K is true but P is true for every integer between the base case and K. If you make that assumption and then go on to prove that P of K plus one is true, then P will be true for all integers N greater than or equal to M. So the main difference here, really the only difference between the second principle of induction and what we've learned already is the inductive hypothesis. Here the inductive hypothesis is stronger. We're assuming the truth of the predicate not only for just a single unspecified value of the variable but for all values of the variable up to an including that unspecified value. Since the hypothesis is stronger, you'll sometimes see this referred to as strong induction. So in terms of our staircase metaphor, this is saying that if we can get on the staircase to begin with, and if we assume that we can step on every step from the bottom up to a certain point, then we can get to the next step. But maybe I don't need to step on the K step to get to the K plus first step. Maybe I have super jumping powers, and as long as I can get somewhere up a stairwell, I can leap from there all the way up to the K plus first step. And the jumping powers aren't so super that I can just jump onto the top without getting to the stairwell in the first place. There's still a base case to be considered. So let's put the second principle to work in our proposition. We're going to see this is a very short proof. We can keep the base case P of two because that doesn't change with the different flavors of induction we use. What is different is the inductive hypothesis. So let's pick the proof up following the base case. So let's assume that for some natural number K, every integer between two and K, including two and including K, can be factored into a product of prime. So this is the strong inductive hypothesis we're making here. We want to show that K plus one can be factored into a product of primes. We're going to consider two cases here. Case one is if K plus one itself is a prime number, and case two is if K plus one isn't a prime number. That's a valid set of cases because every natural number is either prime or not, and no number is both. So in case one, if K plus one is prime, we're done, because a single prime is just a one-term product. And so K plus one can be quote factored into a product of primes. In case two, we're going to assume that K plus one is not prime. That's what we call a composite. It's a factor, it's a multiple of two integers. We can factor K plus one in this case. We don't necessarily know that we can factor it into primes, but we can factor it into say K plus one is A times B where A and B are natural numbers. Now in this case, A and B can be chosen less than K plus one because K plus one isn't prime itself. And so here's where the inductive hypothesis comes in. Because A and B are natural numbers, the inductive hypothesis says that each one of them can be factored into a product of primes. Let's say that A is factored into the product P1 times P2 times P3 and so on up to P sub X, let's say, and all those Ps are prime numbers. And similarly, B can be factored into a bunch primes, let's Q1, Q2 and so forth up to Q sub Y. So how do we get K plus one's factorization? Well just simply by substitution. Just multiply those two strings that primes together, and we're going to get K plus one, which is equal to A times B is actually equal to all the Ps multiplied together times all the Qs multiplied together. And then we're done. We have written K plus one as a product of prime numbers. So just like with the example of 2,001, if we knew the factorization of 667, then we can get the factorization of 2,001 just by importing that factorization. I can take K plus one, and if I can split it at all, I can use the two factorizations to get the factorization of K plus one. And that finishes the proof. So that's the second principle of induction, or again, sometimes called strong induction, which allows us to use induction in cases where there's no natural connection between the K case and the K plus one case. Thanks for watching.