Strong Induction

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: So now we come to an interesting variant of ordinary induction called strong induction, and here's how it works. With strong induction, just as with ordinary induction, you prove the base case P of 0. You're trying to prove for all nP of n, so you prove P of 0, but now in order to prove P of n plus 1 in the inductive step, assuming P of n with ordinary induction, with strong induction you can assume not just P of n but you can assume P of 0, P of 1. All the properties-- that all the numbers up through n have the property. And from this, of course, you could conclude that that everything has the property that for all mP of m.

Now, an intuitive way to justify this is you think about it the way that induction works is you start off at 0, and then you make a step to 1, and you make another step to 2, and you make another step to 3, and the induction step going from n to n plus 1 justifies each of those steps. By the time you get to n and you have to prove you can get to n plus 1, you've already been through 0 1 up to n. You might as well take advantage of that fact.

Instead of only remembering that you're at the n step, you might as well remember that you got there. That's an intuitive hand-wavy argument which can be justified formally in a way that will emerge in the next segment. So let's hold off on that and just bite the bullet and accept this as a basic principle of math that we're going to live with and use.

As an application of it, let's prove something that we've already proved by well ordering and, in fact, strong induction and well ordering are closely related, as we'll also discuss later. So let's prove that using $0.03 and $0.05 stamps that you can get any amount of postage greater than or equal to $0.08 stamps, and I'm going to prove this by strong induction, with the induction hypothesis P of n that says I can form n plus $0.8 stamps. Clearly, if I can prove for all nP of n, then I've proved that I can get for every amount greater than or equal to $0.08 stamps. And let's do the base case.

Well, the base case, P of 0. Can I make $0.8 stamps? Sure, $0.03 and $0.05. That's that one, and that's OK. For the inductive step, I have to get m-- I'm allowed to assume, rather, that I can get m plus $0.8 for any m from n down to 0, instead of just assuming that I can get n plus $0.8 to get n plus 1 plus $0.08. I can assume any amount less than what I'm aiming for, so I may as well assume that I can get any amount of postage from $0.08 up to n plus $0.08, and my objective then is to get n plus 1 plus $0.08, namely n plus $0.09.

So I have to prove that for all n greater than or equal to 0, I can get n plus $0.09, assuming I can get from $0.08 to n plus $0.08. Well, that's not too hard to do. The inductive step is actually going to break up into a couple of cases, depending on the value of n. I have to prove n plus $0.09 for all n, so suppose n equals 0, I have to get $0.09. Well, three $0.03. If n is 1, I have to get 1 plus $0.09 or $0.10, two $0.05. So those cases are disposed of.

So now my job is to get n plus $0.09, where n is greater than or equal to 2. Well, the nice thing about n being greater than or equal to 2 is that if I subtract 2 from it, it's a smaller number, and it's still not negative, and that means that I can get that amount plus $0.08 stamps. So I'm in this nice situation where I, by strong induction, I can get n minus 2 plus $0.08 stamps. There they are. And how do I get to n plus 9? Well, it's easy. I add a $0.03 stamp, and you have n plus $0.09, which completes the proof of the induction case, and the whole theorem is proved. We can conclude then that it works for all n and that you can indeed get n plus $0.08 using $0.03 and $0.05 stamps for all of them. So much for that example.

All right, let's look at another example. This is a game that we used to play in class. You start off with a stack of blocks, say 10 blocks, and you're allowed to make a move that consists of splitting the stack into two smaller stacks. So if the stack has height a plus b, you can split it into a stack of height a and a stack of height b, and you get a score for that move. The score is a times b. And then you keep doing that until you can't make anymore moves. That is, when all you have left are stacks of height one, which you can't split anymore, and then your overall score is the total that you got for all the moves that you made until that point.

Now, when we played this in class, we would have students competing, and they would try various strategies. So one strategy-- the simplest strategy, maybe not the best, but the simplest strategy, would be to start off with a stack of 10, so you take one of, and that leaves you with a stack of one and nine. Your score is nine. Then you take another one off of the stack of nine, and you're left with a one and an eight. Your score is eight, and so on, and you can see, in fact, if took one-at-a-time process then your score with a stack of height n would be n minus 1 plus n minus 2, down to 2 plus 1.

Another strategy that might be sort of more in the spirit of computer science would be to keep splitting in two. So for example, if you had a stack of height 10, you could split it into two fives, and then you take one of the fives and split it into three and a two, and then you'd split the two into two ones, and so on, splitting as evenly as you can each time, and it seems like it might be a better strategy. And, again, we would have students try various strategies, and guess what? They all came in in a tie, and that's what we're going to prove now.

Every way of unstacking n blocks gives the same score. Well, what score? Well, we know that the score for the simple strategy of taking one block off at a time is the sum from 1 to n minus 1, and that has a nice formula-- n times n minus 1 over 2, so we can formulate our claim that no matter how you play the unstacking game with the stack of size n, your final score will be n times n minus 1 over 2, and we're going to prove this by strong induction, with this statement-- call it claim of n-- is going to be the induction hypothesis. That's what we're trying to prove.

Well, let's start in the usual way. The base case is n equals 0. Well, you might be bothered. That's no blocks. Well, let's see what happens. With no blocks, the score is 0 because there's nothing to do, and indeed the formula that is alleged to be your score comes out to be 0, so the base case n equals 0 works.

Let's continue. For the inductive case, I have to assume that the given score formula holds for all stacks of height n or less, and I have to prove that it holds for a stack of height n plus 1. That is, that an n plus 1 stack score is n plus 1 times n over 2. Well, how shall I do that? Well, I'm going to split the inductive case into two cases. It turns out that I need to prove that c of n plus 1 holds, assuming c of n for n and less than n but, in particular, let's just deal with the case that n plus 1 is 1, the smallest value it could have and knock that one off separately. Namely, if the stack is of height one, again my score is 0, because there's no move to make, and the formula still evaluates to 0. So in the case that n plus 1 is 1, I've proved the claim at n plus 1, which I was obligated to do for the base case-- for the inductive step.

Well, the other case in the inductive step is that n plus 1 is greater than 1. This is the interesting one, because now it's possible to make a move. So since n plus 1 is greater than 1, it's two or more blocks. I can make a move into two stacks that are both of positive. So suppose I do that? Suppose I split the stack of size n plus 1 into an a stack and a b stack, where a and b sum to n plus 1.

And what's my score going to be then? Well, my score on that move that I make, where I split into the a stack and the b stack is a b, and the rest of the game consists of playing as well as I can on the a stack and as well as I can on the b stack, but a and b are smaller than n plus 1. They're less than or equal to n, which means that by strong induction, I know that no matter how I play on the a stack, I'm going to wind up with this score a times a minus 1 over 2.

No matter how I play on the b stack, I'm going to wind up with b times b minus 1 over 2, so that means that my score on a plus b stack is going to be this formula, ab plus a times a minus 1 over 2 plus b times b minus 1 over 2. So you simplify that to organize it so it's a plus b times a plus b minus 1, which is exactly n plus 1 times n over 2, which is what we were trying to prove. We've proved C event plus 1. The inductive step is complete, and indeed we've proved that no matter how big the stack is, your score comes out the same.

Free Downloads

Video


Caption

  • English-US (SRT)