College Algebra: Examples of Induction

This lesson has not been reviewed.

Please purchase the lesson to review.

So I want to illustrate the power of this induction method of proof to prove that certain formulas actually hold. So the first one I thought we'd take a look at is the following really neat formula. If you want to add up the first n natural numbers, so you want to add 1 + 2 + 3 + 4, all the way up to some number n, it turns out that that formula for that is always . And I want to prove that to you, using induction.
So remember how the induction method goes. I first have to prove that the very first statement holds, assume it's true for one statement and prove it follows that the next statement is true. Now, it looks like there's only one statement here, so what are the different statements? Well, there's one statement for every single n. When n = 1, this says something. When n = 2, it says something else. When n = 3, it says something else, and so forth. So let's look at what's sometimes referred to as the base case, and we're going to prove this using induction.
So the base case, which is the first case, is when n = 1. So we just check that. We check to see that this is true and we check to see it's true by just looking at the left side and making sure it does equal the right side. We have to verify the formula. Well here I just take 1 and I go up to 1. So, in fact, this is sort of an empty sum, it's just the 1. I go 1 and I don't count anything. n = 1. So, in fact, I don't start at all, I just go, "1". Now does that equal this side? Well, let's put in n = 1 and see what this gives me. This gives me a 1 (1 + 1), which is 2, divided by 2. Well, that is 1. So, in fact, this checks. This is true when n = 1, because this side is 1 and that side is 1. So the formula holds in that first case. So that's pushing the first domino.
Now what I've got to do is convince ourselves that if one domino were to fall, that would force the other domino next to it to fall. So what I do is I assume that the formula's true, that's an assumption, I assume the formula holds when n is some particular value. Let me just call it k. And now my mission is that we want to show the formula holds when n = the next number, k + 1. So I'm assuming that the k-th domino has fallen and I want to now show you that forces the next domino the fall, the k + first domino. What does it mean for the formula to hold when n = k? It means that if I put in k in place of n, that must be a true statement, so let's see what that means. It means that I can just assert, because I'm assuming, that, in fact, 1 + 2, all the way out to k, I'm assuming that does equal the right answer. I'm assuming that domino has fallen. So that's what I am assuming.
Now what I want to do is show that this holds when I put in a k + 1 here. So what do I do? Well, let's just consider what happens when we put in k + 1. In fact, let me do that this way, let me use my divide and conquer method. So I'm assuming this is true, and now I want to look at what happens when, in fact, I put in a k + 1 here. So let's take a look. By putting k + 1, what I see is a 1 + 2 and I go all the way out. I've got k, but then I add one more, I add k + 1. And my hope, I want to try to prove to you that the answer is what I would get in this formula if I put in a k + 1 right in there. That's what I have to now show you.
Well, what can I do? What do I know? Well, what I know is, I'm assuming that I know the sum of the first k numbers. So, in fact, this sum right in here, I know the answer to that. That sum equals this. So in place of this, I could insert that. So let's do that, since we're assuming this is really true, this in really valid, in place of this, I'm going to put in that. So what I would see is . But don't forget that I have to now add that extra k + 1 out in front, because this is just the sum of the first k terms and I've got that k + 1 thing sitting out there.
Well, now it's just a little bit of algebra. Let's get a common denominator and combine. If I get a common denominator, I have to put this here, and then I have a common bottom and I can just add. I would see . And notice there's a common factor of k + 1. It's a factor here and a factor here, so let me factor it out. If I factor it out, what do I see? I see . You see that? Well, there's the k + 1 common factor and, after I factor it out, what am I left with? A k here plus a 2 here. So, in fact, that's the right answer.
So, in fact, I see that the sum of the first k + 1 things is equal to this. I've shown that just under the assumption that this formula holds when I put a k in here. But look at this! This is the exact right-hand side of this formula, if I put in k + 1 for n. Let's check. If I put in a k + 1 here for n, I would see k + 1. If I put a k +1 in right here for n, that would be k + 1 + 1. That's . So, in fact, I just proved to you that this formula will hold if I add up the first k + 1 numbers, just under the assumption that the formula holds if I add up just the first k numbers. So I just showed you the following principle: If this domino were to fall, that forces the next domino to fall. Well, since I know the first domino fell, I actually proved that in the base case, that means the second domino must fall, by this principle. So that means the third domino must fall, the fourth domino must fall, the fifth domino must fall. All dominos fall. This thing has been proven for every single n you can think of. So I just proved that this formula actually holds, no matter what the n is.
Okay, well if I have a little bit more time left, I actually maybe can do one more example. Let's see how much time I have left. I'm finding out right now. I've got 5 minutes, so let's actually look at another example. There's a person here with a whip, by the way, that tells me how much time I have.
Okay, how about this? Let's actually prove the following formula. Let's prove that if you take 2 + 4 + 8, and that is, you just add up all the powers of 2, so I add up all the way to 2^n, let me actually show you that the formula for this is going to be 2(2n - 1). So, in fact, if you ever want to add up the powers of 2, 2, 4, 8, 16, up to 2^n, it just equals that. That's the answer. And let's prove this by induction.
So let's look at the base case. That's the first case, that's to see if the first domino falls. That's when n = 1. So what happens when n = 1? Well, let's just see what the left-hand side looks like, the right-hand side, and see if they're the same. Well, the left-hand side is just 2^1, so there's none of these terms here. n = 1, so it just basically starts off, it's just 2. So the left-hand side I just have a 2 and the question is does that equal the right-hand side? Well, that's what? 2 times - and if I put n = 1 in here, I see 2^1. 2^1 is just 2, 2 - 1 is just 1. So I see 2 1. Well, does 2 = 2 1? It sure does. So, in fact, this checks. So the first domino falls.
Now what I have to do is I have to assume that this formula holds for an arbitrary domino and prove the next domino must fall. So, as you can see over here, I'm going to now assume that this formula holds when n = k. What that means is 2 + 4 + 8, all the way up to 2^k, that will equal 2(2^k - 1). So that's my inductive hypothesis. That's what I'm assuming. And what do I want to show? I want to prove that the formula is going to hold when I put in a k + 1 for n.
Okay, well let's take a look at the left-hand side, where we have k + 1. Well, that would be 2 + 4 + 8, all the way out to 2^k, but then I add that last term, 2^k + 1. Now I want to see what that equals. Well, look, I already know what the first few terms look like, because I know that if I add up 2, up to 2^k, which appears right here, what I know is that that equals this thing. So I can actually put that in right now and I can put in the fact that this equals 2(2^k - 1), and then I have to add a plus 2^k + 1.
Okay, so that's what I have here. Now, let's see, does that look sort of at all interesting, reasonable, anything? Well, I don't know, it looks okay, but let's see if we can sort of make this look like it's supposed to look. So, let's see, I guess the first thing I would do, see this thing here is that. Okay, so one thing I could do, for example, would be to either distribute this 2 here that might not be a bad idea. In fact, let's do that and see what happens. If I were to distribute this here, by the way, you might not know what to do next. If you don't know what to do next, just try something. Don't be paralyzed by the fear of the unknown. If you don't know how to do something, just try something and if you fail, you fail. Not a big deal. Let's distribute that 2, so if I see 2(2^k), that's 2^k + 1, and then here I see a 2 - 1, so that's -2, then I see plus 2^k + 1. That's that last term there. So this red was just distributed here. But look, I have (2^k + 1) + (2^k + 1). So, how many 2^k + 1's do I have? I have two of them. So, in fact, this equals 2(2^k + 1), because I have two of them. Don't forget that -2. And now, actually, I'm feeling pretty good, because I see a common factor of 2 here and here, so let me factor that out. If I factor it out, I see 2(2^k + 1) - 1. So that's the answer that we got. But notice that's exactly what the formula predicts we should get, if n = k + 1. Because notice if I add up the first k + 1 things here, powers of 2, the formula says I should get 2, well there's a 2, times 2^k + 1 - 1. So, in fact, just assuming that the formula holds in the k position, I'm now able to deduce and prove and verify, using that, that it's true in the k + 1^st position. That means that what I just proved was that if this domino were to fall, it would force the next domino to fall. And since I know the first domino falls, because I checked, that forces the second domino to fall, which forces the third domino to fall, which forces the fourth domino. So, in fact, for any n you can think of, this holds.
That's the power of induction. You can prove infinitely many things. This holds for infinitely many n's, all in a finite number of steps. A really powerful means to prove a theorem.
All right, try some of these induction things and try to think about what's going on here. It's really cool, just a little bit of algebra and you can do it. See you soon.
Further Topics in Algebra
Induction
Examples of Inductions Page [3 of 3]